Skip to main content

7.4 - Recursion

7.4.1 - Recursion Overview​

  • Definition: Recursion is a programming technique where a function calls itself to solve a problem. Each time the function calls itself, it works on a smaller piece of the problem.

  • Base Case: This is a condition that stops the recursion. Without a base case, a recursive function would call itself indefinitely, leading to a stack overflow.

  • Recursive Case: The part of the function that includes the recursive call. Here, the function tackles a smaller part of the problem until it reaches the base case.

7.4.2 - Recursion Basic Structure​

def recursive_function(parameters):
    if base_case_condition:
        return base_case_solution
    else:
        # Recursive call with modified parameters
        return recursive_function(modified_parameters)

7.4.3 - Recursion Examples​

7.4.3.1 - Example 1: Factorial Function​

def factorial(n):
    if n == 0 or n == 1:  # Base case
        return 1
    else:
        return n * factorial(n-1)  # Recursive case

In this example, factorial(n) calls itself with n-1 until it reaches the base case (n == 0 or n == 1).

7.4.3.2 - Example 2: Fibonacci Sequence​

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

7.4.3.3 - Example 3: Sum of Natural Numbers​

A simple example where we calculate the sum of the first n natural numbers using recursion.

def sum_natural_numbers(n):
    if n <= 1:
        return n
    else:
        return n + sum_natural_numbers(n - 1)

# Example usage
print(sum_natural_numbers(5))  # Outputs 15 (1+2+3+4+5)

In this function, we add the current number n to the sum of numbers from 1 to n-1, which is obtained through the recursive call.

7.4.3.4 - Example 4: Binary Search​

Binary search can be implemented recursively to find the position of an element in a sorted list.

def binary_search(arr, low, high, x):
    if high >= low:
        mid = (high + low) // 2

        # If element is present at the middle
        if arr[mid] == x:
            return mid

        # If element is smaller than mid, it's in the left subarray
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)

        # Else, it's in the right subarray
        else:
            return binary_search(arr, mid + 1, high, x)

    else:
        # Element is not present in array
        return -1

# Example usage
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, 0, len(arr)-1, x)
print("Element is present at index", str(result))

Here, the function divides the search interval in half and calls itself recursively for the half in which the target value may lie.

7.4.3.5 - Example 5: Tower of Hanoi​

The Tower of Hanoi is a classic example of a recursive problem. It involves moving disks from one peg to another with certain rules.

def tower_of_hanoi(n, from_rod, to_rod, aux_rod):
    if n == 1:
        print(f"Move disk 1 from rod {from_rod} to rod {to_rod}")
        return
    tower_of_hanoi(n - 1, from_rod, aux_rod, to_rod)
    print(f"Move disk {n} from rod {from_rod} to rod {to_rod}")
    tower_of_hanoi(n - 1, aux_rod, to_rod, from_rod)

# Example usage
n = 3
tower_of_hanoi(n, 'A', 'C', 'B')  # A, B, C are the names of rods

This function moves n disks from one rod to another using an auxiliary rod, ensuring that a larger disk never sits on top of a smaller disk.

7.4.4 - Best Practices and Considerations​

  1. Base Case: Ensure your recursion has a clear base case to prevent infinite recursion.

  2. Memory Usage: Each recursive call adds a layer to the stack, which can lead to high memory usage. Python has a recursion limit (which can be checked or modified with sys.getrecursionlimit() and sys.setrecursionlimit()).

  3. Tail Recursion Optimization: Python does not support tail call optimization. Thus, deep recursive calls can cause a stack overflow.

  4. Iterative Alternatives: Sometimes, an iterative solution is more efficient than recursion, especially for problems that involve simple loops.

  5. Debugging: Debugging recursive functions can be tricky. Use print statements or a debugger to track how your function behaves with each recursive call.