Recursion

Why read this? Some problems are naturally recursive — a problem contains a smaller version of itself. Think of Russian nesting dolls, or the definition of a directory: "a folder contains files and folders." Recursion is the programming technique of a function calling itself to solve such problems.

🎯 Learning Objectives

1. Understand recursion — a function calling itself
2. Identify the base case (stopping condition) and recursive case
3. Write recursive functions for factorial, Fibonacci, and more
4. Trace recursive execution on the call stack
5. Compare recursion vs iteration

📋 Prerequisites

• Functions — Understanding how functions work.
• While Loops — Understanding iterative solutions helps.

📖 Core Content

23.1 What Problem Does Recursion Solve?

23.2 Anatomy of a Recursive Function

1. Base case — the simplest version, solved directly (no recursion)
2. Recursive case — reduce the problem and call yourself

python
Run Inline
# runnable
def countdown(n):
    """Print numbers from n down to 1."""
    if n <= 0:          # Base case
        return
    print(n)            # Do something
    countdown(n - 1)    # Recursive case: call with smaller n
countdown(5)

pseudo
5
4
3
2
1

23.3 The Call Stack

23.4 Factorial with Recursion

python
Run Inline
# runnable
def factorial(n):
    """Compute n! recursively."""
    if n <= 1:            # Base case: 0! = 1, 1! = 1
        return 1
    return n * factorial(n - 1)  # Recursive case
print(factorial(5))   # 120
print(factorial(10))  # 3628800

pseudo
factorial(4) = 4 * factorial(3)
            = 4 * (3 * factorial(2))
            = 4 * (3 * (2 * factorial(1)))
            = 4 * (3 * (2 * 1))
            = 4 * (3 * 2)
            = 4 * 6
            = 24

23.5 Fibonacci with Recursion

python
Run Inline
# runnable
def fibonacci(n):
    """Return the nth Fibonacci number."""
    if n <= 1:          # Base case: F0 = 0, F1 = 1
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)  # Recursive case
for i in range(10):
    print(f"F{i} = {fibonacci(i)}")

pseudo
F0 = 0
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34

23.6 Worked Example 1: Sum of List (Recursive)

python
Run Inline
# runnable
def sum_list(lst):
    """Sum all elements in a list recursively."""
    if not lst:          # Base case: empty list
        return 0
    return lst[0] + sum_list(lst[1:])  # First + rest
print(sum_list([1, 2, 3, 4, 5]))  # 15

23.7 Worked Example 2: String Reversal (Recursive)

python
Run Inline
# runnable
def reverse_string(s):
    """Reverse a string recursively."""
    if len(s) <= 1:      # Base case: empty or single char
        return s
    return reverse_string(s[1:]) + s[0]  # Reverse rest, then add first
print(reverse_string("Python"))  # nohtyP

23.8 Worked Example 3: Power Function (Recursive)

python
Run Inline
# runnable
def power(base, exp):
    """Compute base^exp recursively."""
    if exp == 0:          # Base case: any number^0 = 1
        return 1
    return base * power(base, exp - 1)  # base * base^(exp-1)
print(power(2, 10))  # 1024
print(power(3, 4))   # 81

23.9 Worked Example 4: Palindrome Check (Recursive)

python
Run Inline
# runnable
def is_palindrome(s):
    """Check if string is palindrome recursively."""
    s = s.lower().replace(" ", "")
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])
print(is_palindrome("racecar"))   # True
print(is_palindrome("hello"))     # False
print(is_palindrome("A man a plan a canal panama"))  # True

23.10 Recursion vs Iteration

⚠️ Common Pitfalls

Pitfall 1: Missing Base Case

Pitfall 2: Base Case Never Reached

Pitfall 3: Exponential Recursion (Fibonacci)

📝 Practice Questions

Q1: Trace factorial(3) step by step.

Answer:

pseudo
factorial(3) = 3 * factorial(2)
            = 3 * (2 * factorial(1))
            = 3 * (2 * 1)
            = 3 * 2
            = 6

Q2: Write a recursive function to compute the sum of digits of a number.

Answer:

python
Run Inline
def sum_digits(n):
    if n < 10:
        return n
    return n % 10 + sum_digits(n // 10)
print(sum_digits(1234))  # 10

Q3-10: Additional recursion questions.

(Following pattern.)

🔗 Cross-References

• Next Topic: Binary Search
• Previous Topic: Function Arguments
• Reference: Python for Everybody, Chapter 4 (Section 4.10 — "Fruitful functions" mentions recursion briefly)
• Video: L75: Introduction to recursion, L76: Theoretical introduction to recursion, L77: Recursion illustration Join Discord Previous22. Function ArgumentsNext24. Binary Search