Recursion Fundamentals

Recursion is when a function calls itself to solve smaller instances of the same problem. It's a powerful technique for solving problems that have a recursive structure.

What is Recursion?

Recursion breaks a problem into smaller subproblems of the same type until reaching a simple base case.

def factorial(n):
    # Base case: simplest version
    if n <= 1:
        return 1
    
    # Recursive case: break down the problem
    return n * factorial(n - 1)

# factorial(5) = 5 * factorial(4)
#              = 5 * 4 * factorial(3)
#              = 5 * 4 * 3 * factorial(2)
#              = 5 * 4 * 3 * 2 * factorial(1)
#              = 5 * 4 * 3 * 2 * 1
#              = 120

The Call Stack

When a recursive function calls itself, each call is added to the call stack. The stack grows until the base case is reached, then unwinds as each call returns.

Space Complexity: O(n) for the call stack

Essential Components of Recursion

1. Base Case

The simplest scenario that can be solved directly without recursion.

2. Recursive Case

Breaks the problem into smaller subproblems and calls itself.

3. Progress Toward Base Case

Each recursive call must move closer to the base case to avoid infinite recursion.

Classic Recursion Examples

Fibonacci Sequence

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

Warning: This has O(2^n) time complexity due to repeated calculations!

Sum of Digits

def sum_of_digits(n):
    if n == 0:
        return 0
    return n % 10 + sum_of_digits(n // 10)

Recursion vs Iteration

Binary Search (Recursive)

def binary_search(arr, target, left, right):
    # Base case: not found
    if left > right:
        return -1
    
    mid = (left + right) // 2
    
    # Base case: found
    if arr[mid] == target:
        return mid
    
    # Recursive cases
    if arr[mid] > target:
        return binary_search(arr, target, left, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, right)

Common Pitfalls

Missing Base Case

def infinite_recursion(n):
    return n + infinite_recursion(n - 1)  # No base case!
    # Results in RecursionError

Not Making Progress

def stuck(n):
    if n == 0:
        return 0
    return 1 + stuck(n)  # Always calls stuck(n), never decreases!

Stack Overflow

Too many recursive calls can exceed the stack limit (~1000 calls in Python).

Quiz

Key Takeaways

✅ Recursion solves problems by breaking them into smaller instances
✅ Base case prevents infinite recursion
✅ Call stack stores each recursive call - uses O(n) space
✅ Not always efficient - naive fibonacci is O(2^n)
✅ Best for tree traversal, divide-and-conquer, backtracking

Master recursion for solving complex hierarchical problems! 🚀