A function that calls itself is recursive. It's like looking up a word in a dictionary and finding another word you need to look up — which sends you to another word — until you find one you understand.

Essential Parts of Recursion

1. Base case: A simple case where the answer is known directly. Without this, the recursion never stops.
2. Recursive case: The function calls itself with a smaller version of the original problem.

Example: Factorial

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

Trace for factorial(3):

factorial(3)
→ 3 * factorial(2)
→ 3 * 2 * factorial(1)
→ 3 * 2 * 1
→ 6

Practice 1

1. Write a recursive function to calculate the sum of numbers from 1 to n.
2. What happens if you forget the base case?

How Recursion Uses the Stack

Each recursive call is pushed onto the call stack. When the base case is reached, the calls are popped off in reverse order (Last In, First Out).

Practice 2

1. Write a recursive function to calculate the nth Fibonacci number: fib(n) = fib(n-1) + fib(n-2), with fib(0)=0, fib(1)=1.
2. Trace the recursive calls for fib(4). How many times is fib(2) called?

Many problems become elegant and simple when solved recursively. Let's look at some classic examples.

Recursive Binary Search

def binary_search(items, target, left, right):
    if left > right:
        return -1  # Base case: empty range
    
    mid = (left + right) // 2
    if items[mid] == target:
        return mid  # Base case: found
    elif items[mid] < target:
        return binary_search(items, target, mid + 1, right)
    else:
        return binary_search(items, target, left, mid - 1)

Each recursive call searches a smaller half of the list. The base cases are either finding the target or the range becoming empty.

Practice 1

1. Write a recursive function to sum all elements of a list.
2. Write a recursive function to find the maximum value in a list.

Recursion vs Iteration

Practice 2

1. Implement binary search recursively (as shown above). Test it.
2. Rewrite the iterative binary search as a recursive version. Which do you find clearer?