---
title: "10 Must Practice Python Recursive Programs"
description: "Recursion in Python allows functions to call themselves, solving complex problems like factorial, Fibonacci, and tree traversals through smaller, manageable subproblems efficiently."
url: https://srinimf.com/2024/10/19/10-must-practice-python-recursive-programs/
date: 2024-10-19
modified: 2026-10-10
author: "Srini"
image: https://i0.wp.com/srinimf.com/wp-content/uploads/2024/10/flower-yellow-pot.png?fit=1024%2C768&ssl=1
categories: ["Python"]
tags: ["Recursive programs"]
type: post
lang: en
---

# 10 Must Practice Python Recursive Programs

Recursion is a programming method where a function calls itself to tackle smaller parts of a bigger problem. In Python, it is often used for tasks that can be divided into similar, smaller problems. Here are some typical examples of recursion in Python.

## 1. **Factorial Calculation**

A classic example of recursion is calculating the factorial of a number.

Related[Python Interview Prep in 1 Hour: 12 Essential Coding Programs](https://srinimf.com/2025/09/10/python-interview-prep-in-1-hour-12-essential-coding-programs/)

```
def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

# Example usage
print(factorial(5))  # Output: 120
```

## 2. **Fibonacci Sequence**

The Fibonacci sequence is another well-known problem solved using recursion.

```
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# Example usage
print(fibonacci(6))  # Output: 8
```

## 3. **Sum of a List**

Recursion can be used to calculate the sum of elements in a list.

```
def recursive_sum(lst):
    if not lst:  # Base case: if the list is empty
        return 0
    else:
        return lst[0] + recursive_sum(lst[1:])

# Example usage
print(recursive_sum([1, 2, 3, 4, 5]))  # Output: 15
```

## 4. **Traversing Nested Data Structures (e.g., Nested Lists or Dictionaries)**

Recursion helps traverse or flatten nested data structures like lists or dictionaries.

#### Traversing Nested Lists:

```
def traverse_list(lst):
    for element in lst:
        if isinstance(element, list):
            traverse_list(element)
        else:
            print(element)

# Example usage
nested_list = [1, [2, 3, [4, 5]], 6]
traverse_list(nested_list)  # Output: 1 2 3 4 5 6
```

#### Traversing Nested Dictionaries:

```
def traverse_dict(d):
    for key, value in d.items():
        if isinstance(value, dict):
            traverse_dict(value)
        else:
            print(f"{key}: {value}")

# Example usage
nested_dict = {
    'a': 1,
    'b': {'x': 10, 'y': {'z': 20}},
    'c': 3
}
traverse_dict(nested_dict)
# Output:
# a: 1
# x: 10
# z: 20
# c: 3
```

## 5. **Binary Search**

Recursion can be used to implement binary search, an efficient algorithm for searching sorted lists.

```
def binary_search(arr, target, low, high):
    if low > high:
        return -1  # Target not found
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)
    else:
        return binary_search(arr, target, low, mid - 1)

# Example usage
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(arr, 5, 0, len(arr) - 1))  # Output: 4
```

## 6. **Tower of Hanoi Problem**

This is a classic recursion problem. The goal is to move a set of disks from one rod to another while following certain rules.

```
def hanoi(n, source, destination, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
    else:
        hanoi(n - 1, source, auxiliary, destination)
        print(f"Move disk {n} from {source} to {destination}")
        hanoi(n - 1, auxiliary, destination, source)

# Example usage
hanoi(3, 'A', 'C', 'B')
# Output:
# Move disk 1 from A to C
# Move disk 2 from A to B
# Move disk 1 from C to B
# Move disk 3 from A to C
# Move disk 1 from B to A
# Move disk 2 from B to C
# Move disk 1 from A to C
```

## 7. **Permutations of a String or List**

Recursion is often used to generate all permutations of a string or list.

```
def permutations(s):
    if len(s) == 1:
        return [s]
    else:
        result = []
        for i in range(len(s)):
            for p in permutations(s[:i] + s[i+1:]):
                result.append(s[i] + p)
        return result

# Example usage
print(permutations("abc"))  # Output: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
```

## 8. **Solving Maze Problems**

Recursion is used to explore possible paths in a maze. This approach can be adapted to a wide variety of problems that involve pathfinding.

```
def solve_maze(maze, x, y, solution):
    # Base case: reached the destination
    if x == len(maze) - 1 and y == len(maze[0]) - 1 and maze[x][y] == 1:
        solution[x][y] = 1
        return True

    # Check if maze[x][y] is valid
    if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 1:
        solution[x][y] = 1

        # Move right
        if solve_maze(maze, x, y + 1, solution):
            return True

        # Move down
        if solve_maze(maze, x + 1, y, solution):
            return True

        # If none of the above worked, backtrack
        solution[x][y] = 0
        return False

    return False

# Example usage
maze = [
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 1, 0, 0],
    [1, 1, 1, 1]
]
solution = [[0 for _ in range(len(maze[0]))] for _ in range(len(maze))]
solve_maze(maze, 0, 0, solution)

for row in solution:
    print(row)
# Output (solution path):
# [1, 0, 0, 0]
# [1, 1, 0, 0]
# [0, 1, 0, 0]
# [0, 1, 1, 1]
```

## 9. **Tree Traversals**

Recursion is widely used in tree data structures for traversing trees (in-order, pre-order, post-order).

```
class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value

def in_order_traversal(root):
    if root:
        in_order_traversal(root.left)
        print(root.value, end=" ")
        in_order_traversal(root.right)

# Example usage
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

in_order_traversal(root)  # Output: 4 2 5 1 3
```

## 10. **Divide and Conquer Algorithms**

Recursion is fundamental in divide and conquer algorithms, like merge sort or quicksort.

#### Merge Sort:

```
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print(arr)  # Output: [3, 9, 10, 27, 38, 43, 82]
```

[Also, read: Top Books Data Engineering Code Pipelines](https://srinimf.com/2024/10/18/create-robust-data-pipelines-using-aws-and-databricks-2-top-books/)

### Key Takeaways:

- **Breaking down problems**: Recursion is useful for issues that can be divided into smaller subproblems.
- **Base case**: Every recursive function should have a base case to prevent infinite recursion.
- **Efficiency**: Recursion can make some problems easier to conceptualize. However, it is not always the most efficient solution. This is due to potential overhead in function calls and space complexity.

### Share this:

-
- [Tweet](https://twitter.com/share)
- [![](https://i0.wp.com/assets.pinterest.com/images/pidgets/pinit_fg_en_rect_gray_20.png)](https://www.pinterest.com/pin/create/link/?url=https%3A%2F%2Fsrinimf.com%2F2024%2F10%2F19%2F10-must-practice-python-recursive-programs%2F&media=https%3A%2F%2Fi0.wp.com%2Fsrinimf.com%2Fwp-content%2Fuploads%2F2024%2F10%2Fflower-yellow-pot.png%3Ffit%3D1024%252C768%26ssl%3D1&description=10%20Must%20Practice%20Python%20Recursive%20Programs)
-
- [Share on Tumblr](https://www.tumblr.com/share)
- [Share on WhatsApp (Opens in new window) WhatsApp](https://srinimf.com/2024/10/19/10-must-practice-python-recursive-programs/?share=jetpack-whatsapp)
- [More](#)
-

- [Print (Opens in new window) Print](https://srinimf.com/2024/10/19/10-must-practice-python-recursive-programs/?share=print)
- [Share on Reddit (Opens in new window) Reddit](https://srinimf.com/2024/10/19/10-must-practice-python-recursive-programs/?share=reddit)
- [Share on Telegram (Opens in new window) Telegram](https://srinimf.com/2024/10/19/10-must-practice-python-recursive-programs/?share=telegram)
- [Email a link to a friend (Opens in new window) Email](mailto:?subject=%5BShared%20Post%5D%2010%20Must%20Practice%20Python%20Recursive%20Programs&body=https%3A%2F%2Fsrinimf.com%2F2024%2F10%2F19%2F10-must-practice-python-recursive-programs%2F&share=email)
-

### Like this:

Like Loading…