Recursion and Recursive Thinking

📖 Introduction

Recursion was the concept that made me feel like a "real" programmer. The first time I saw a function calling itself, it felt like magic—and also deeply confusing. How can something define itself in terms of itself without creating an infinite loop?

The breakthrough came when I stopped thinking of recursion as a function calling itself and started thinking of it as breaking a problem into smaller identical problems. Once I understood the call stack and learned to trust that smaller subproblems would be solved correctly, recursion became one of the most elegant tools in my programming toolkit.

This article demystifies recursion with clear mental models and practical Python examples.

---

🎯 What Is Recursion?

Recursion is a problem-solving approach where a function solves a problem by solving smaller instances of the same problem.

The Two Essential Components

1. Base Case: The simplest version of the problem that can be solved directly

2. Recursive Case: Break the problem down and call the function on smaller inputs

def factorial(n: int) -> int:
    """
    Calculate n! = n × (n-1) × (n-2) × ... × 1
    
    Base case: 0! = 1 or 1! = 1
    Recursive case: n! = n × (n-1)!
    """
    # Base case
    if n <= 1:
        return 1
    
    # Recursive case
    return n * factorial(n - 1)


# Trace factorial(5):
# 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)))
#              = 5 * (4 * (3 * 2))
#              = 5 * (4 * 6)
#              = 5 * 24
#              = 120

---

📚 Understanding the Call Stack

Every function call creates a stack frame containing local variables and return address. Recursion builds up stack frames until hitting a base case, then unwinds.

Visualizing the Stack

def countdown(n: int) -> None:
    """Simple countdown to visualize stack."""
    print(f"  " * (5 - n) + f"countdown({n}) called")
    
    if n == 0:
        print(f"  " * (5 - n) + f"Base case reached!")
        return
    
    countdown(n - 1)
    print(f"  " * (5 - n) + f"countdown({n}) returning")


countdown(5)

# Output:
# countdown(5) called
#   countdown(4) called
#     countdown(3) called
#       countdown(2) called
#         countdown(1) called
#           countdown(0) called
#           Base case reached!
#         countdown(1) returning
#       countdown(2) returning
#     countdown(3) returning
#   countdown(4) returning
# countdown(5) returning

Stack Frame Contents

import sys

def show_stack_depth(n: int, depth: int = 0) -> None:
    """Show how stack grows with recursion."""
    frame_size = sys.getsizeof(depth) + sys.getsizeof(n)
    print(f"Depth {depth}: n={n}, approx frame size={frame_size} bytes")
    
    if n == 0:
        return
    
    show_stack_depth(n - 1, depth + 1)


show_stack_depth(5)

# Each recursive call adds a new frame to the stack
# Deep recursion can cause stack overflow

Python's Recursion Limit

import sys

# Default recursion limit
print(f"Default limit: {sys.getrecursionlimit()}")  # Usually 1000

# Can be increased (carefully!)
sys.setrecursionlimit(2000)

# But there's also the system stack limit
# Exceeding it causes a segmentation fault, not a Python exception

def deep_recursion(n: int) -> int:
    if n == 0:
        return 0
    return 1 + deep_recursion(n - 1)


# This will hit RecursionError around 1000
try:
    deep_recursion(1500)
except RecursionError as e:
    print(f"RecursionError: {e}")

---

🎨 Designing Base Cases

Good base cases are crucial. They must:

1. Eventually be reached

2. Return correct values

3. Handle edge cases

Common Base Case Patterns

# Pattern 1: Zero/Empty
def sum_list(lst: list) -> int:
    """Sum of all elements."""
    if not lst:  # Empty list
        return 0
    return lst[0] + sum_list(lst[1:])


# Pattern 2: Single Element
def find_max(lst: list) -> int:
    """Maximum element."""
    if len(lst) == 1:
        return lst[0]
    rest_max = find_max(lst[1:])
    return lst[0] if lst[0] > rest_max else rest_max


# Pattern 3: Two Elements
def gcd(a: int, b: int) -> int:
    """Greatest common divisor using Euclidean algorithm."""
    if b == 0:
        return a
    return gcd(b, a % b)


# Pattern 4: Boolean Condition
def is_palindrome(s: str) -> bool:
    """Check if string is palindrome."""
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])


# Pattern 5: Multiple Base Cases
def fibonacci(n: int) -> int:
    """Fibonacci sequence."""
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

Base Case Errors

# ERROR: Missing base case - infinite recursion
def bad_factorial(n: int) -> int:
    return n * bad_factorial(n - 1)  # Never stops!


# ERROR: Wrong base case value
def bad_sum(lst: list) -> int:
    if not lst:
        return 1  # Should be 0!
    return lst[0] + bad_sum(lst[1:])


# ERROR: Base case never reached
def bad_countdown(n: int) -> None:
    if n == 0:
        return
    bad_countdown(n - 2)  # What if n is odd?


# FIXED: Handle both even and odd
def countdown_fixed(n: int) -> None:
    if n <= 0:  # <= instead of ==
        return
    print(n)
    countdown_fixed(n - 1)

---

🔄 Recursive Patterns

Pattern 1: Linear Recursion

Process one element, recurse on the rest.

def reverse_string(s: str) -> str:
    """
    Reverse a string recursively.
    Time: O(n), Space: O(n) for stack
    """
    if len(s) <= 1:
        return s
    return reverse_string(s[1:]) + s[0]


def count_occurrences(lst: list, target) -> int:
    """Count how many times target appears."""
    if not lst:
        return 0
    count = 1 if lst[0] == target else 0
    return count + count_occurrences(lst[1:], target)


def filter_positive(lst: list) -> list:
    """Keep only positive numbers."""
    if not lst:
        return []
    rest = filter_positive(lst[1:])
    if lst[0] > 0:
        return [lst[0]] + rest
    return rest

Pattern 2: Binary Recursion (Divide and Conquer)

Split problem in half, solve both halves.

def merge_sort(arr: list) -> list:
    """
    Sort using divide and conquer.
    Time: O(n log n), Space: O(n)
    """
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)


def merge(left: list, right: list) -> list:
    """Merge two sorted lists."""
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result


def binary_search_recursive(arr: list, target: int, left: int = 0, right: int = None) -> int:
    """
    Find target in sorted array.
    Time: O(log n), Space: O(log n) for stack
    """
    if right is None:
        right = len(arr) - 1
    
    if left > right:
        return -1
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

Pattern 3: Tree Recursion

Multiple recursive calls for branching structures.

from typing import Optional
from dataclasses import dataclass

@dataclass
class TreeNode:
    val: int
    left: Optional['TreeNode'] = None
    right: Optional['TreeNode'] = None


def tree_height(node: Optional[TreeNode]) -> int:
    """
    Calculate tree height.
    Time: O(n), Space: O(h) where h is height
    """
    if node is None:
        return 0
    
    left_height = tree_height(node.left)
    right_height = tree_height(node.right)
    
    return 1 + max(left_height, right_height)


def tree_sum(node: Optional[TreeNode]) -> int:
    """Sum all values in tree."""
    if node is None:
        return 0
    
    return node.val + tree_sum(node.left) + tree_sum(node.right)


def count_nodes(node: Optional[TreeNode]) -> int:
    """Count nodes in tree."""
    if node is None:
        return 0
    
    return 1 + count_nodes(node.left) + count_nodes(node.right)

Pattern 4: Mutual Recursion

Functions call each other.

def is_even(n: int) -> bool:
    """Check if n is even using mutual recursion."""
    if n == 0:
        return True
    return is_odd(n - 1)


def is_odd(n: int) -> bool:
    """Check if n is odd using mutual recursion."""
    if n == 0:
        return False
    return is_even(n - 1)


# Practical example: Expression parser
def parse_expression(tokens: list) -> int:
    """Parse: expr = term (('+' | '-') term)*"""
    result = parse_term(tokens)
    
    while tokens and tokens[0] in ['+', '-']:
        op = tokens.pop(0)
        right = parse_term(tokens)
        if op == '+':
            result += right
        else:
            result -= right
    
    return result


def parse_term(tokens: list) -> int:
    """Parse: term = factor (('*' | '/') factor)*"""
    result = parse_factor(tokens)
    
    while tokens and tokens[0] in ['*', '/']:
        op = tokens.pop(0)
        right = parse_factor(tokens)
        if op == '*':
            result *= right
        else:
            result //= right
    
    return result


def parse_factor(tokens: list) -> int:
    """Parse: factor = number | '(' expr ')'"""
    if tokens[0] == '(':
        tokens.pop(0)  # Remove '('
        result = parse_expression(tokens)
        tokens.pop(0)  # Remove ')'
        return result
    return int(tokens.pop(0))

---

💾 Memoization

Memoization caches results to avoid redundant computation.

The Problem: Overlapping Subproblems

import functools

# Naive Fibonacci - O(2^n) exponential!
call_count = 0

def fib_naive(n: int) -> int:
    global call_count
    call_count += 1
    
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


# fib_naive(35) makes millions of calls!
# Many subproblems are solved repeatedly

The Solution: Cache Results

# Manual memoization
def fib_memo(n: int, cache: dict = None) -> int:
    if cache is None:
        cache = {}
    
    if n in cache:
        return cache[n]
    
    if n <= 1:
        return n
    
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]


# Using functools.lru_cache (preferred)
@functools.lru_cache(maxsize=None)
def fib_cached(n: int) -> int:
    """
    O(n) time, O(n) space with memoization.
    """
    if n <= 1:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)


# Comparison
import time

# Without memo: ~30 seconds for fib(40)
# With memo: instant for fib(1000)

When to Use Memoization

# Good candidate: Overlapping subproblems
@functools.lru_cache(maxsize=None)
def count_paths(m: int, n: int) -> int:
    """Count paths in m×n grid from top-left to bottom-right."""
    if m == 1 or n == 1:
        return 1
    return count_paths(m - 1, n) + count_paths(m, n - 1)


# Good candidate: Expensive computation
@functools.lru_cache(maxsize=128)
def expensive_calculation(x: int) -> int:
    """Cache expensive results."""
    # Simulate expensive computation
    import time
    time.sleep(0.1)
    return x * x


# NOT a good candidate: No repeated calls
def factorial(n: int) -> int:
    """Each subproblem solved only once - memo doesn't help."""
    if n <= 1:
        return 1
    return n * factorial(n - 1)

---

🔀 Tail Recursion

Tail recursion is when the recursive call is the last operation.

Regular vs Tail Recursion

# Regular recursion - must wait for return value
def factorial_regular(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial_regular(n - 1)  # Multiply AFTER return


# Tail recursion - recursive call is last operation
def factorial_tail(n: int, accumulator: int = 1) -> int:
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)  # Nothing after call


# Trace regular factorial(4):
# factorial(4) = 4 * factorial(3)
#              = 4 * (3 * factorial(2))
#              = 4 * (3 * (2 * factorial(1)))
#              = 4 * (3 * (2 * 1))
#              = 4 * (3 * 2)
#              = 4 * 6
#              = 24

# Trace tail factorial(4, 1):
# factorial_tail(4, 1)
# factorial_tail(3, 4)     # accumulator = 4 * 1
# factorial_tail(2, 12)    # accumulator = 3 * 4
# factorial_tail(1, 24)    # accumulator = 2 * 12
# return 24

Why Tail Recursion Matters

# Tail recursion can be optimized to iteration (Tail Call Optimization)
# Python does NOT do TCO, but other languages do

# Converting tail recursion to iteration manually:
def factorial_iterative(n: int) -> int:
    """Equivalent to tail recursive version."""
    accumulator = 1
    while n > 1:
        accumulator *= n
        n -= 1
    return accumulator


# More tail recursion examples
def sum_list_tail(lst: list, accumulator: int = 0) -> int:
    """Tail recursive sum."""
    if not lst:
        return accumulator
    return sum_list_tail(lst[1:], accumulator + lst[0])


def reverse_tail(lst: list, accumulator: list = None) -> list:
    """Tail recursive reverse."""
    if accumulator is None:
        accumulator = []
    if not lst:
        return accumulator
    return reverse_tail(lst[1:], [lst[0]] + accumulator)

---

🔄 Converting Between Recursion and Iteration

Recursion to Iteration

# Recursive version
def sum_recursive(n: int) -> int:
    if n == 0:
        return 0
    return n + sum_recursive(n - 1)


# Iterative version
def sum_iterative(n: int) -> int:
    total = 0
    for i in range(1, n + 1):
        total += i
    return total


# Using explicit stack for complex recursion
def tree_sum_iterative(root: Optional[TreeNode]) -> int:
    """Convert recursive tree traversal to iterative."""
    if root is None:
        return 0
    
    stack = [root]
    total = 0
    
    while stack:
        node = stack.pop()
        total += node.val
        
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return total

Iteration to Recursion

# Iterative version
def power_iterative(base: int, exp: int) -> int:
    result = 1
    for _ in range(exp):
        result *= base
    return result


# Recursive version
def power_recursive(base: int, exp: int) -> int:
    if exp == 0:
        return 1
    return base * power_recursive(base, exp - 1)


# Optimized recursive version (O(log n))
def power_fast(base: int, exp: int) -> int:
    if exp == 0:
        return 1
    if exp % 2 == 0:
        half = power_fast(base, exp // 2)
        return half * half
    else:
        return base * power_fast(base, exp - 1)

When to Use Which

Use Recursion When	Use Iteration When
Problem has recursive structure	Simple loop suffices
Tree/graph traversal	Performance is critical
Divide and conquer	Deep recursion possible
Code clarity matters	Memory is limited
Memoization helps	Tail recursion converts easily

---

🧩 Classic Recursive Problems

Tower of Hanoi

def hanoi(n: int, source: str, target: str, auxiliary: str) -> None:
    """
    Solve Tower of Hanoi puzzle.
    
    Move n disks from source to target using auxiliary.
    Time: O(2^n), Space: O(n)
    """
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    
    # Move n-1 disks from source to auxiliary
    hanoi(n - 1, source, auxiliary, target)
    
    # Move largest disk from source to target
    print(f"Move disk {n} from {source} to {target}")
    
    # Move n-1 disks from auxiliary to target
    hanoi(n - 1, auxiliary, target, source)


# hanoi(3, 'A', 'C', 'B')
# Move disk 1 from A to C
# Move disk 2 from A to B
# Move disk 1 from C to B
# Move disk 3 from A to C
# Move disk 1 from B to A
# Move disk 2 from B to C
# Move disk 1 from A to C

Generate Permutations

def permutations(arr: list) -> list:
    """
    Generate all permutations.
    Time: O(n!), Space: O(n!)
    """
    if len(arr) <= 1:
        return [arr]
    
    result = []
    for i, elem in enumerate(arr):
        # Fix one element, permute the rest
        rest = arr[:i] + arr[i+1:]
        for perm in permutations(rest):
            result.append([elem] + perm)
    
    return result


# permutations([1, 2, 3])
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Generate Subsets (Power Set)

def subsets(arr: list) -> list:
    """
    Generate all subsets.
    Time: O(2^n), Space: O(2^n)
    """
    if not arr:
        return [[]]
    
    first = arr[0]
    rest_subsets = subsets(arr[1:])
    
    # Subsets without first + subsets with first
    with_first = [[first] + subset for subset in rest_subsets]
    return rest_subsets + with_first


# subsets([1, 2, 3])
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Flood Fill

def flood_fill(
    image: list[list[int]],
    row: int,
    col: int,
    new_color: int
) -> list[list[int]]:
    """
    Fill connected region with new color (like paint bucket).
    Time: O(m*n), Space: O(m*n) for recursion
    """
    rows, cols = len(image), len(image[0])
    original_color = image[row][col]
    
    if original_color == new_color:
        return image
    
    def fill(r: int, c: int) -> None:
        # Boundary check
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        
        # Color check
        if image[r][c] != original_color:
            return
        
        # Fill this cell
        image[r][c] = new_color
        
        # Recurse to neighbors
        fill(r + 1, c)
        fill(r - 1, c)
        fill(r, c + 1)
        fill(r, c - 1)
    
    fill(row, col)
    return image

---

📝 Practice Exercises

Exercise 1: Sum of Digits

def sum_digits(n: int) -> int:
    """
    Return sum of digits of n recursively.
    sum_digits(123) -> 6 (1 + 2 + 3)
    """
    # Your implementation here
    pass

Solution

def sum_digits(n: int) -> int:
    if n < 10:
        return n
    return n % 10 + sum_digits(n // 10)

Exercise 2: Flatten Nested List

def flatten(nested: list) -> list:
    """
    Flatten arbitrarily nested list.
    flatten([1, [2, [3, 4], 5], 6]) -> [1, 2, 3, 4, 5, 6]
    """
    # Your implementation here
    pass

Solution

def flatten(nested: list) -> list:
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

Exercise 3: String Combinations

def combinations(s: str, k: int) -> list:
    """
    Generate all k-length combinations of characters in s.
    combinations("abc", 2) -> ["ab", "ac", "bc"]
    """
    # Your implementation here
    pass

Solution

def combinations(s: str, k: int) -> list:
    if k == 0:
        return [""]
    if len(s) < k:
        return []
    
    # Include first char + combinations of rest with k-1
    with_first = [s[0] + c for c in combinations(s[1:], k - 1)]
    
    # Exclude first char + combinations of rest with k
    without_first = combinations(s[1:], k)
    
    return with_first + without_first

---

🔑 Key Takeaways

1. Base cases stop recursion—ensure they're always reached

2. The call stack stores state for each recursive call

3. Memoization eliminates redundant computation

4. Tail recursion can be converted to iteration

5. Trust the recursion—assume smaller problems are solved correctly

6. Visualize the problem tree to understand complexity

---

🚀 What's Next?

In the next article, we'll explore arrays and strings:

• Python list and string internals

• Two-pointer techniques

• Sliding window algorithms

• Common array/string problems

Next: Article 4 - Arrays and Strings

---

📚 References

• CLRS Chapter 4: Divide-and-Conquer

• Python's functools.lru_cache documentation

• "Structure and Interpretation of Computer Programs" - Recursion chapters