Recursion

Recursion is a powerful technique where a function calls itself to solve a problem by breaking it down into smaller subproblems. It's elegant for problems with natural recursive structure - like tree traversal, mathematical sequences, and divide-and-conquer algorithms. Understanding recursion opens doors to solving complex problems with surprisingly simple code!

Recursion Basics

A recursive function has two essential parts: a base case that stops the recursion, and a recursive case that calls the function with a smaller problem. Without a base case, recursion continues forever (until Python raises a RecursionError).

Click Run to execute your code

Practical Recursion Examples

Recursion is perfect for problems that can be expressed in terms of smaller versions of themselves: calculating Fibonacci numbers, reversing strings, summing lists, and checking palindromes. Let's see these classic patterns in action.

Click Run to execute your code

Recursion with Nested Structures

Recursion truly shines when working with nested or tree-like data structures. Traversing nested dictionaries, flattening lists of lists, or processing file systems becomes elegant with recursion - the function naturally handles any level of nesting.

Click Run to execute your code

Optimization and When to Avoid Recursion

Naive recursion can be slow due to redundant calculations (like in Fibonacci). Memoization caches results to avoid recalculating. Sometimes, an iterative solution is simpler, faster, and avoids stack overflow - know when to use each approach.

Click Run to execute your code

Common Mistakes

# Wrong - no base case, infinite recursion!
def count_down(n):
    print(n)
    count_down(n - 1)  # Never stops!

# Correct - include base case
def count_down(n):
    if n <= 0:  # Base case
        return
    print(n)
    count_down(n - 1)

# Wrong - n never decreases!
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n)  # Should be (n-1)!

# Correct - progress toward base case
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)  # n decreases

# Overcomplicated recursion
def sum_list(lst, index=0):
    if index >= len(lst):
        return 0
    return lst[index] + sum_list(lst, index + 1)

# Simpler iteration
def sum_list(lst):
    total = 0
    for item in lst:
        total += item
    return total

# Or just use built-in!
total = sum(lst)

# Wrong - missing return!
def factorial(n):
    if n <= 1:
        return 1
    factorial(n - 1) * n  # Result not returned!

# Correct - return the result
def factorial(n):
    if n <= 1:
        return 1
    return factorial(n - 1) * n

# Wrong - crashes on negative numbers
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

factorial(-3)  # Infinite recursion!

# Correct - handle edge cases
def factorial(n):
    if n < 0:
        raise ValueError("Factorial not defined for negative numbers")
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Exercise: Binary Search

Click Run to execute your code

def binary_search(arr, target, low=0, high=None):
    """Recursively search for target in sorted array."""
    if high is None:
        high = len(arr) - 1

    # Base case: not found
    if low > high:
        return -1

    mid = (low + high) // 2

    # Base case: found
    if arr[mid] == target:
        return mid

    # Recursive cases
    if arr[mid] > target:
        return binary_search(arr, target, low, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, high)

# Test it
numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(f"Search for 7: index {binary_search(numbers, 7)}")
print(f"Search for 15: index {binary_search(numbers, 15)}")
print(f"Search for 6: index {binary_search(numbers, 6)}")

Summary

What's Next?

Congratulations on completing the Functions module! You now have powerful tools for writing reusable, modular code. Next, we'll explore Modules and Packages - how to organize your code into files, import functionality, and use Python's vast ecosystem of third-party packages!