Recursion Introduction - Python Programming

Many programming problems involve repeating the same operation on smaller pieces of data, like calculating compound interest or navigating folder structures. Recursion provides an elegant way to solve these problems by having a function call itself with progressively simpler inputs until reaching a trivial case.

Characteristics

Elegant: solves complex problems with simple code
Memory: uses call stack
Performance: often slower than iteration
Natural fit: trees, graphs, divide-and-conquer

When to Use

Problem naturally recursive
Divide and conquer algorithms
Backtracking problems
Mathematical sequences

When to Avoid

Simple loops work better
Very deep recursion
Performance critical code
Python recursion limit concerns

Fibonacci Example

base_case.py

# Importance of base case

import sys


def infinite_recursion(n):
    """Missing base case (don't run!)"""
    # No base case - will cause RecursionError
    return infinite_recursion(n - 1)


def countdown(n):
    """Correct with base case"""
    # Base case
    if n <= 0:
        print("Liftoff!")
        return 0

    # Recursive case
    print(n)
    return countdown(n - 1)


def bad_base_case(n):
    """Wrong base case"""
    # Base case never reached for negative input
    if n == 0:
        return 0
    return bad_base_case(n - 1)


# Test base cases
print("Countdown with proper base case:")
countdown(5)

print("\nTrying infinite recursion with small depth:")
# Set a smaller recursion limit for demonstration
old_limit = sys.getrecursionlimit()
sys.setrecursionlimit(20)

try:
    # This will overflow quickly
    infinite_recursion(10)
except RecursionError:
    print("RecursionError caught!")

# Restore original limit
sys.setrecursionlimit(old_limit)

print("\nWrong base case with positive input (safe):")
bad_base_case(3)
print("Completed successfully")

# Uncommenting this will cause RecursionError
# print("\nWrong base case with negative input:")
# bad_base_case(-5)

factorial.py

# Basic factorial recursion


def factorial(n):
    """Recursive factorial"""
    # Base case
    if n <= 1:
        return 1

    # Recursive case
    # n! = n × (n-1)!
    return n * factorial(n - 1)


# Test factorial
limit = 
for i in range(limit):
    print(f"{i}! = {factorial(i)}")

print(f"\n10! = {factorial(10)}")

# Basic factorial recursion


def factorial(n):
    """Recursive factorial"""
    # Base case
    if n <= 1:
        return 1

    # Recursive case
    # n! = n × (n-1)!
    return n * factorial(n - 1)


# Test factorial
limit = 
for i in range(limit):
    print(f"{i}! = {factorial(i)}")

print(f"\n10! = {factorial(10)}")

# Basic factorial recursion


def factorial(n):
    """Recursive factorial"""
    # Base case
    if n <= 1:
        return 1

    # Recursive case
    # n! = n × (n-1)!
    return n * factorial(n - 1)


# Test factorial
limit = 
for i in range(limit):
    print(f"{i}! = {factorial(i)}")

print(f"\n10! = {factorial(10)}")

trace.py

# Factorial with trace


depth = 0


def factorial(n):
    """Factorial with trace"""
    global depth

    # Indent based on depth
    indent = "  " * depth

    print(f"{indent}→ factorial({n})")
    depth += 1

    # Base and recursive cases
    if n <= 1:
        result = 1
        print(f"{indent}  Base case: return 1")
    else:
        result = n * factorial(n - 1)
        print(f"{indent}  Return {n} * factorial({n-1}) = {result}")

    depth -= 1
    print(f"{indent}← returning {result}")

    return result


# Test with trace
print("Computing factorial(5):\n")
result = factorial(5)
print(f"\nFinal result: {result}")

vs_iteration.py

# Recursion vs iteration

import time


def sum_recursive(n):
    """Recursive sum"""
    # Base case
    if n <= 0:
        return 0
    # Recursive case
    return n + sum_recursive(n - 1)


def sum_iterative(n):
    """Iterative sum"""
    # Loop approach
    total = 0
    for i in range(1, n + 1):
        total += i
    return total


def power_recursive(base, exp):
    """Recursive power"""
    # Base case
    if exp == 0:
        return 1
    # Recursive case
    return base * power_recursive(base, exp - 1)


def power_iterative(base, exp):
    """Iterative power"""
    # Loop approach
    result = 1
    for _ in range(exp):
        result *= base
    return result


# Compare both approaches
print("Sum 1 to 10:")
print(f"  Recursive: {sum_recursive(10)}")
print(f"  Iterative: {sum_iterative(10)}")

print("\n2^8:")
print(f"  Recursive: {power_recursive(2, 8)}")
print(f"  Iterative: {power_iterative(2, 8)}")

# Performance comparison kept small so trace replay stays readable.
n = 12

start = time.perf_counter()
r1 = sum_recursive(n)
time_recursive = time.perf_counter() - start

start = time.perf_counter()
r2 = sum_iterative(n)
time_iterative = time.perf_counter() - start

print(f"\nPerformance (sum to {n}):")
print(f"  Recursive: {time_recursive * 1000:.4f} ms")
print(f"  Iterative: {time_iterative * 1000:.4f} ms")
print(f"  Speedup:   {time_recursive / time_iterative:.2f}x")

fibonacci.py

# Fibonacci sequence


def fibonacci(n):
    """Recursive fibonacci"""
    # Base cases
    if n <= 1:
        return n

    # Recursive case
    # fib(n) = fib(n-1) + fib(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2)


# Fibonacci with call counting
call_count = 0


def fibonacci_counted(n):
    """Fibonacci with call counting"""
    global call_count
    call_count += 1

    if n <= 1:
        return n

    return fibonacci_counted(n - 1) + fibonacci_counted(n - 2)


# Test fibonacci
print("Fibonacci sequence:")
for i in range(7):
    print(f"fib({i}) = {fibonacci(i)}")

# Count calls for fib(6)
call_count = 0
result = fibonacci_counted(6)
print(f"\nfib(6) = {result}, required {call_count} calls")

# Count calls for fib(8)
call_count = 0
result = fibonacci_counted(8)
print(f"fib(8) = {result}, required {call_count} calls")

base_case The condition where recursion stops and returns a direct value without further recursive calls

factorial A mathematical function where n! = n * (n-1) * ... * 1, naturally expressed recursively

Exercise: practical.py

Implement a recursive countdown function and a recursive sum of digits function