Recursion & Divide-and-Conquer

Recursion Basics

Recursion is a fundamental programming technique where a function calls itself to solve a problem. It's based on the principle of solving a problem by breaking it down into smaller, similar subproblems. Recursion is particularly powerful for problems that have a natural recursive structure, such as tree traversals, mathematical sequences, and divide-and-conquer algorithms.

Essential Components of Recursion

Every recursive function must have two critical components:

• Base Case: A condition that stops the recursion and returns a value without making further recursive calls. Without a base case, recursion would continue infinitely, causing a stack overflow.
• Recursive Case: The function calls itself with a smaller or simpler version of the problem, moving closer to the base case with each call.

Classic Example: Factorial

The factorial of a number n (n!) is the product of all positive integers from 1 to n. This is a natural recursive problem because n! = n × (n-1)!.

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

# Example: factorial(5)
# factorial(5) = 5 * factorial(4)
# factorial(4) = 4 * factorial(3)
# factorial(3) = 3 * factorial(2)
# factorial(2) = 2 * factorial(1)
# factorial(1) = 1 (base case)
# Result: 5 * 4 * 3 * 2 * 1 = 120

Understanding the Call Stack

When a recursive function executes, each recursive call is added to the call stack. The stack grows until the base case is reached, then unwinds as each function returns its value. Understanding this process is crucial for debugging recursive functions.

def countdown(n):
    if n <= 0:  # Base case
        print("Blastoff!")
        return
    print(n)
    countdown(n - 1)  # Recursive call

# Execution trace for countdown(3):
# countdown(3) prints 3, calls countdown(2)
# countdown(2) prints 2, calls countdown(1)
# countdown(1) prints 1, calls countdown(0)
# countdown(0) prints "Blastoff!", returns
# Stack unwinds: countdown(1) returns, countdown(2) returns, countdown(3) returns

More Recursive Examples

Sum of Array Elements

Note the arr[1:] in the version below: slicing copies the remainder of the list at every level, so this apparently linear function actually runs in O(n²) time and allocates O(n²) memory in total. It is a trap worth recognising — the slice looks free and is not. The indexed version that follows is genuinely O(n).

# O(n²) - each slice copies the rest of the list
def sum_array(arr):
    # Base case: empty array has sum 0
    if len(arr) == 0:
        return 0
    # Recursive case: sum = first element + sum of rest
    return arr[0] + sum_array(arr[1:])

# O(n) - pass an index instead of building a new list
def sum_array_indexed(arr, i=0):
    if i == len(arr):
        return 0
    return arr[i] + sum_array_indexed(arr, i + 1)

# Example: sum_array([1, 2, 3, 4])
# = 1 + sum_array([2, 3, 4])
# = 1 + 2 + sum_array([3, 4])
# = 1 + 2 + 3 + sum_array([4])
# = 1 + 2 + 3 + 4 + sum_array([])
# = 1 + 2 + 3 + 4 + 0 = 10

String Reversal

The same slicing cost applies here, compounded by Python strings being immutable — every + builds a new string. This is O(n²); it is shown because the recursive structure is clear, not because you should write it this way.

def reverse_string(s):
    # Base case: empty string or single character
    if len(s) <= 1:
        return s
    # Recursive case: reverse rest + first character
    return reverse_string(s[1:]) + s[0]

# Example: reverse_string("hello")
# = reverse_string("ello") + "h"
# = reverse_string("llo") + "e" + "h"
# = reverse_string("lo") + "l" + "e" + "h"
# = reverse_string("o") + "l" + "l" + "e" + "h"
# = "o" + "l" + "l" + "e" + "h" = "olleh"

Power Calculation

def power(base, exponent):
    # Base case: any number to the power of 0 is 1
    if exponent == 0:
        return 1
    # Recursive case: base^exponent = base * base^(exponent-1)
    return base * power(base, exponent - 1)

# Optimized version using divide-and-conquer (exponentiation by squaring):
def power_optimized(base, exponent):
    # Handle negatives first. Without this, a negative exponent alternates
    # between the two branches below forever and overflows the stack.
    if exponent < 0:
        return 1 / power_optimized(base, -exponent)
    if exponent == 0:
        return 1
    if exponent % 2 == 0:
        # If exponent is even: base^exp = (base^2)^(exp/2)
        return power_optimized(base * base, exponent // 2)
    else:
        # If exponent is odd: base^exp = base * base^(exp-1)
        return base * power_optimized(base, exponent - 1)

The naive version makes n recursive calls: O(n). Squaring halves the exponent at every second step, so it makes O(log n) calls: O(log n). For power(2, 1000) that is 1000 multiplications versus about 20. The same trick underlies modular exponentiation in RSA, where the exponents have hundreds of digits and the naive version is not merely slow but impossible.

Divide and Conquer

Divide and conquer is a powerful algorithmic paradigm that solves problems by breaking them into smaller, independent subproblems, solving each subproblem recursively, and then combining the solutions to solve the original problem. This approach is particularly effective for problems that can be naturally divided into similar subproblems.

The Three-Step Process

1. Divide: Break the problem into smaller subproblems of the same type. The subproblems should be independent and similar in structure to the original problem.
2. Conquer: Solve the subproblems recursively. If a subproblem is small enough, solve it directly (base case).
3. Combine: Merge the solutions of the subproblems to form the solution to the original problem.

Master Theorem

The Master Theorem gives the time complexity of divide-and-conquer algorithms directly, without unrolling the recursion. For a recurrence of the form:

T(n) = a T(n/b) + f(n)

where a ≥ 1, b > 1, and f(n) is asymptotically positive: a is the number of subproblems, n/b is their size, and f(n) is the cost of splitting and recombining. Everything hinges on comparing f(n) against the watershed function n^log_ba, which is the total work done at the leaves of the recursion tree.

The three cases

Case 1 — leaves dominate. If f(n) = O(n^{log_ba − ε}) for some ε > 0, then:

T(n) = Θ(n^log_ba)

Case 2 — every level costs the same. If f(n) = Θ(n^log_ba log^kn) for some k ≥ 0, then:

T(n) = Θ(n^log_ba log^k+1n)

Case 3 — the root dominates. If f(n) = Ω(n^{log_ba + ε}) for some ε > 0, and the regularity condition a f(n/b) ≤ c f(n) holds for some c < 1 and all sufficiently large n, then:

T(n) = Θ(f(n))

Worked examples

Merge sort:      T(n) = 2T(n/2) + Θ(n)
                 a=2, b=2  →  n^(log₂2) = n¹ = n
                 f(n) = Θ(n) = Θ(n¹ log⁰n)      → Case 2 with k=0
                 T(n) = Θ(n log n)

Binary search:   T(n) = 1T(n/2) + Θ(1)
                 a=1, b=2  →  n^(log₂1) = n⁰ = 1
                 f(n) = Θ(1) = Θ(1 · log⁰n)      → Case 2 with k=0
                 T(n) = Θ(log n)

Strassen:        T(n) = 7T(n/2) + Θ(n²)
                 a=7, b=2  →  n^(log₂7) ≈ n^2.807
                 f(n) = O(n^(2.807-ε))              → Case 1
                 T(n) = Θ(n^log₂7) ≈ Θ(n^2.807)

Naive matmul:    T(n) = 8T(n/2) + Θ(n²)
                 a=8, b=2  →  n^(log₂8) = n³
                 f(n) = O(n^(3-ε))                  → Case 1
                 T(n) = Θ(n³)

When the theorem does not apply

There are gaps between the cases. If f(n) grows faster than n^log_ba but not polynomially faster, no case matches — T(n) = 2T(n/2) + n log n is the classic example (the answer is Θ(n log² n), obtainable from the recursion tree). Case 3 also fails if the regularity condition does not hold. The theorem further assumes subproblems are all the same size; for uneven splits such as T(n) = T(n/3) + T(2n/3) + n, use the Akra–Bazzi method instead.

When the Master Theorem cannot be applied, fall back on drawing the recursion tree and summing level by level, or guessing an answer and proving it by substitution (induction).

Classic Example: Merge Sort

Merge Sort is a perfect illustration of divide-and-conquer. It divides the array in half, sorts each half recursively, and then merges the sorted halves.

def merge_sort(arr):
    # Base case: array with 0 or 1 element is already sorted
    if len(arr) <= 1:
        return arr
    
    # Divide: split array into two halves
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # Conquer: sort left half
    right = merge_sort(arr[mid:])   # Conquer: sort right half
    
    # Combine: merge the sorted halves
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    # Merge two sorted arrays
    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
    
    # Add remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Time Complexity: O(n log n)
# Space Complexity: O(n)

Binary Search

Binary search uses divide-and-conquer to find an element in a sorted array by repeatedly dividing the search space in half.

def binary_search(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    
    # Base case: element not found
    if left > right:
        return -1
    
    # Divide: find middle element.
    # left + (right - left) // 2 rather than (left + right) // 2 - equivalent in
    # Python, but the habit matters in fixed-width languages where left + right
    # can overflow. This was a real bug in the JDK's binary search for nine years.
    mid = left + (right - left) // 2
    
    # Conquer: check if target is at mid, left, or right
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        # Search left half
        return binary_search(arr, target, left, mid - 1)
    else:
        # Search right half
        return binary_search(arr, target, mid + 1, right)

# Time Complexity: O(log n)
# Space Complexity: O(log n) due to recursion

Maximum Subarray Problem (Divide-and-Conquer)

Find the contiguous subarray with the largest sum, by taking the best of three candidates: the maximum subarray entirely in the left half, entirely in the right half, or crossing the midpoint.

Note that this is not Kadane's algorithm, despite the two often being conflated. Kadane's is a single O(n) left-to-right scan and is covered in Dynamic Programming. The divide-and-conquer version below is O(n log n) — strictly worse — but it is a clean illustration of the paradigm, and the contrast between the two is instructive: sometimes recognising the right recurrence beats splitting the problem in half.

def max_subarray(arr, low, high):
    # Base case: single element
    if low == high:
        return arr[low]
    
    # Divide: find middle
    mid = (low + high) // 2
    
    # Conquer: find max in left and right halves
    left_max = max_subarray(arr, low, mid)
    right_max = max_subarray(arr, mid + 1, high)
    
    # Combine: find max crossing the middle
    cross_max = max_crossing_subarray(arr, low, mid, high)
    
    return max(left_max, right_max, cross_max)

# Call as: max_subarray(arr, 0, len(arr) - 1)   -- requires a non-empty array

def max_crossing_subarray(arr, low, mid, high):
    # Find max sum in left half including mid
    left_sum = float('-inf')
    total = 0
    for i in range(mid, low - 1, -1):
        total += arr[i]
        left_sum = max(left_sum, total)
    
    # Find max sum in right half excluding mid
    right_sum = float('-inf')
    total = 0
    for j in range(mid + 1, high + 1):
        total += arr[j]
        right_sum = max(right_sum, total)
    
    return left_sum + right_sum

# Time Complexity: O(n log n)

Quick Sort

Quick Sort uses divide-and-conquer by selecting a pivot, partitioning the array around the pivot, and recursively sorting the partitions.

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        # Divide: partition array and get pivot index
        pivot_index = partition(arr, low, high)
        
        # Conquer: sort elements before and after partition
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    # Choose rightmost element as pivot
    pivot = arr[high]
    i = low - 1  # Index of smaller element
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Average Time Complexity: O(n log n)
# Worst Case: O(n²)

When to Use Divide-and-Conquer

• Problems can be divided into similar subproblems
• Subproblems are independent (solutions don't overlap)
• Combining solutions is straightforward
• Base cases are easy to identify and solve
• Examples: sorting, searching, mathematical computations, tree operations

Memoization

Memoization is an optimization technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again. This dramatically improves performance for recursive functions that solve overlapping subproblems, reducing time complexity from exponential to polynomial in many cases.

Why Memoization Matters

Without memoization, recursive functions like Fibonacci recompute the same values multiple times. For example, computing fibonacci(5) requires computing fibonacci(3) twice, fibonacci(2) three times, and fibonacci(1) five times. Memoization eliminates this redundant computation.

Fibonacci with Memoization

# Naive recursive approach (inefficient)
def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)
# Time Complexity: O(2^n) - exponential!

# Memoized version (efficient)
#
# The cache is a default argument bound to None and created per top-level call,
# NOT a module-level `memo = {}`. A shared global cache keyed on a bare integer
# collides with every other function that also keys on an integer - see the
# warning below.
def fibonacci(n, memo=None):
    if memo is None:
        memo = {}

    # Check if result already computed
    if n in memo:
        return memo[n]

    # Base cases
    if n <= 1:
        return n

    # Compute and store result
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]
# Time Complexity: O(n) - linear!
# Space Complexity: O(n)

Why not a module-level cache? Writing memo = {} at module scope is a common shortcut, and it breaks as soon as two memoized functions share the module. Both fibonacci and climb_stairs below key their cache on a plain integer, so a shared dict means whichever runs first poisons the other:

# With a shared module-level `memo`:
fibonacci(10)      → 55    correct
climb_stairs(10)   → 55    WRONG - the correct answer is 89

# fibonacci already stored memo[10] = 55, and climb_stairs returns it verbatim.

Always scope the cache to the call (the memo=None idiom above), or use functools.cache, which handles this correctly and automatically.

Using Python's functools.lru_cache

Python provides a built-in decorator for memoization that handles caching automatically.

from functools import cache          # Python 3.9+

@cache
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# On Python < 3.9, the equivalent is:
#     from functools import lru_cache
#     @lru_cache(maxsize=None)
#
# The cache is keyed on the full argument tuple AND scoped to this specific
# function, so neither of the failure modes described above can occur.
# Use @lru_cache(maxsize=N) instead when you want a bounded cache.

Two caveats: arguments must be hashable, so you cannot memoize a function that takes a list, and the cache holds strong references to its arguments, so decorating a method keeps every self it has seen alive for the lifetime of the process.

Memoization Pattern

The general pattern for implementing memoization:

def memoized_function(n, memo=None):
    if memo is None:
        memo = {}
    
    # Check cache first
    if n in memo:
        return memo[n]
    
    # Base case
    if base_case(n):
        result = base_value
    else:
        # Recursive case - compute result
        result = compute(n, memoized_function)
    
    # Store result in cache
    memo[n] = result
    return result

More Memoization Examples

Climbing Stairs Problem

Count ways to reach the nth step if you can take 1 or 2 steps at a time.

def climb_stairs(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]

    # Base cases
    if n == 0 or n == 1:
        return 1

    # Ways to reach n = ways to reach (n-1) + ways to reach (n-2)
    memo[n] = climb_stairs(n - 1, memo) + climb_stairs(n - 2, memo)
    return memo[n]

# Without memoization: O(2^n)
# With memoization: O(n)

Grid Paths (Unique Paths)

Count unique paths from top-left to bottom-right in a grid, moving only right or down.

def unique_paths(m, n, memo=None):
    if memo is None:
        memo = {}
    key = (m, n)
    if key in memo:
        return memo[key]

    # Base case: reached destination
    if m == 1 or n == 1:
        return 1

    # Paths = paths from top + paths from left
    memo[key] = unique_paths(m - 1, n, memo) + unique_paths(m, n - 1, memo)
    return memo[key]

# Time Complexity: O(m * n) with memoization
# Without memoization: O(2^(m+n))

Longest Common Subsequence

def lcs(s1, s2, i=0, j=0, memo=None):
    if memo is None:
        memo = {}
    key = (i, j)                    # safe: this cache belongs to THIS (s1, s2) pair
    if key in memo:
        return memo[key]

    # Base case: end of string
    if i == len(s1) or j == len(s2):
        return 0

    # If characters match, include in LCS
    if s1[i] == s2[j]:
        result = 1 + lcs(s1, s2, i + 1, j + 1, memo)
    else:
        # Try both possibilities
        result = max(lcs(s1, s2, i + 1, j, memo), lcs(s1, s2, i, j + 1, memo))

    memo[key] = result
    return result

This one deserves particular care. With a module-level cache keyed on (i, j) the strings themselves are not part of the key, so results leak between completely unrelated inputs:

lcs("ABCDE", "ACE")   → 3    correct
lcs("XYZ",   "QRS")   → 3    WRONG - the correct answer is 0

Scoping the cache per call, as above, fixes it. If you prefer @cache, include the strings in the signature so they form part of the key.

Memoization vs Tabulation

Memoization (top-down) and tabulation (bottom-up) are both dynamic programming techniques. Memoization is often more intuitive as it closely follows the recursive structure, while tabulation builds solutions iteratively from the base cases.

• Memoization: Top-down approach, cache results as you compute them
• Tabulation: Bottom-up approach, build table from base cases (see Dynamic Programming)

Common Recursive Patterns

Understanding common recursive patterns helps you recognize when recursion is the right approach and how to structure your solution. Here are the most important patterns you'll encounter.

1. Tree/Graph Traversal

Recursion is natural for tree and graph structures. Each node can be processed, and then its children/neighbors are processed recursively.

# Binary Tree Traversal
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root):
    result = []
    if root:
        result.extend(inorder_traversal(root.left))  # Left
        result.append(root.val)                        # Root
        result.extend(inorder_traversal(root.right))   # Right
    return result

# Depth-First Search (DFS) on Graph
def dfs(graph, node, visited):
    visited.add(node)
    print(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Watch the recursion limit. Python's default cap is 1000 frames, so recursive DFS raises RecursionError on a graph with a path longer than that — and a linked list or a degenerate tree of 10,000 nodes is not an unusual input. Prefer the iterative stack-based version for graphs of unknown size. Raising sys.setrecursionlimit is not a real fix: the C stack can still overflow and segfault the interpreter.

See Graph Algorithms and Trees for detailed coverage.

2. Backtracking

Backtracking uses recursion to explore all possible solutions by trying partial solutions and abandoning them if they can't lead to a valid solution.

# Generate all permutations
#
# Track which POSITIONS are used, not which values. Testing `if num not in current`
# compares by value, so it silently skips genuine permutations whenever the input
# contains duplicates - permute([1, 1, 2]) would return [] instead of 3 results.
# The membership test is also O(n), which would make the whole thing O(n · n!).
def permute(nums):
    result = []
    used = [False] * len(nums)

    def backtrack(current):
        # Base case: permutation complete
        if len(current) == len(nums):
            result.append(current[:])
            return

        # Try each unused position
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            current.append(nums[i])      # Make choice
            backtrack(current)           # Recurse
            current.pop()                # Undo choice (backtrack)
            used[i] = False

    backtrack([])
    return result

# To emit only DISTINCT permutations when the input has duplicates, sort first
# and skip an element whose identical predecessor is unused at this level:
#     if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue

# N-Queens Problem
def solve_n_queens(n):
    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    
    def is_safe(row, col):
        # Check column
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        # Check diagonals
        for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
            if board[i][j] == 'Q':
                return False
        for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
            if board[i][j] == 'Q':
                return False
        return True
    
    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if is_safe(row, col):
                board[row][col] = 'Q'    # Place queen
                backtrack(row + 1)       # Recurse
                board[row][col] = '.'    # Remove queen (backtrack)
    
    backtrack(0)
    return result

3. Dynamic Programming

Many dynamic programming problems have recursive solutions that can be optimized with memoization. The recursive structure helps identify overlapping subproblems.

# Coin Change Problem
def coin_change(coins, amount, memo=None):
    if memo is None:
        memo = {}
    if amount in memo:
        return memo[amount]

    if amount == 0:
        return 0
    if amount < 0:
        return float('inf')

    min_coins = float('inf')
    for coin in coins:
        result = coin_change(coins, amount - coin, memo)
        if result != float('inf'):
            min_coins = min(min_coins, 1 + result)

    memo[amount] = min_coins
    return min_coins

# Returns float('inf') when the amount cannot be made. LeetCode 322 expects -1,
# so wrap it:  r = coin_change(coins, amount); return -1 if r == float('inf') else r

See Dynamic Programming for comprehensive coverage.

4. Recursive Data Structures

Many data structures are naturally recursive, making recursion the ideal approach for operations on them.

# Linked List Operations
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_linked_list(head):
    # Base case: empty list or single node
    if not head or not head.next:
        return head
    
    # Reverse the rest of the list
    reversed_rest = reverse_linked_list(head.next)
    
    # Make next node point to current
    head.next.next = head
    head.next = None
    
    return reversed_rest

# Binary Tree Operations
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

5. Mathematical Sequences

Many mathematical problems have natural recursive definitions.

# Pascal's Triangle
# NOTE: no memoization here, so this is O(2^row) - it recomputes the same
# entries exponentially many times, exactly like naive Fibonacci. Add a
# memo=None cache keyed on (row, col) to make it O(row × col).
def pascal_triangle(row, col):
    # Base cases
    if col == 0 or col == row:
        return 1
    # Recursive case: sum of two numbers above
    return pascal_triangle(row - 1, col - 1) + pascal_triangle(row - 1, col)

# Catalan Numbers
def catalan(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return 1
    result = 0
    for i in range(n):
        result += catalan(i, memo) * catalan(n - 1 - i, memo)
    memo[n] = result
    return result

6. String/Array Processing

Many string and array problems can be solved recursively by processing one element and recursively handling the rest.

# Generate all subsets
def subsets(nums):
    result = []
    
    def backtrack(index, current):
        # Add current subset
        result.append(current[:])
        
        # Try adding each remaining element
        for i in range(index, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    
    backtrack(0, [])
    return result

# Generate all combinations
def combinations(n, k):
    result = []
    
    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        
        for i in range(start, n + 1):
            current.append(i)
            backtrack(i + 1, current)
            current.pop()
    
    backtrack(1, [])
    return result

Recursion vs Iteration

Both recursion and iteration can solve many problems. Understanding when to use each is crucial for writing efficient code.

When to Use Recursion

• Problem has natural recursive structure (trees, graphs, divide-and-conquer)
• Solution is more intuitive and readable with recursion
• Problem size is bounded (won't cause stack overflow)
• Backtracking or exploring multiple paths

When to Use Iteration

• Simple loops are more efficient
• Stack overflow is a concern (deep recursion)
• Performance is critical (iteration is usually faster)
• Problem has clear iterative structure

Converting Recursion to Iteration

Many recursive functions can be converted to iterative versions using stacks or by identifying the iterative pattern.

# Recursive factorial
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

# Iterative factorial
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Recursive DFS
def dfs_recursive(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# Iterative DFS using stack
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(reversed(graph[node]))  # Reverse to maintain order
    return visited

Common Pitfalls and Debugging Tips

Common Mistakes

1. Missing or Incorrect Base Case: Leads to infinite recursion and stack overflow.
2. Not Making Progress: Recursive call must move toward base case (e.g., n-1, not n).
3. Modifying Shared State: Be careful with global variables or mutable default arguments.
4. Forgetting Return Statement: Recursive calls must return values to combine results.
5. Stack Overflow: Deep recursion can exhaust the call stack (typically ~1000-3000 calls).

Debugging Techniques

# Add print statements to trace execution
def factorial_debug(n, depth=0):
    indent = "  " * depth
    print(f"{indent}factorial({n}) called")
    
    if n <= 1:
        print(f"{indent}Base case: returning 1")
        return 1
    
    result = n * factorial_debug(n - 1, depth + 1)
    print(f"{indent}factorial({n}) returning {result}")
    return result

# Use a wrapper to track calls
def count_calls(func):
    def wrapper(*args, **kwargs):
        wrapper.call_count += 1
        print(f"Call #{wrapper.call_count}: {func.__name__}{args}")
        return func(*args, **kwargs)
    wrapper.call_count = 0
    return wrapper

@count_calls
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Tail Recursion

Tail recursion occurs when the recursive call is the last operation. Some languages optimize tail recursion, but Python doesn't. However, understanding tail recursion helps convert to iterative solutions.

# Not tail recursive (multiplication after recursive call)
def factorial_not_tail(n):
    if n <= 1:
        return 1
    return n * factorial_not_tail(n - 1)  # Operation after recursion

# Tail recursive version
def factorial_tail(n, accumulator=1):
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)  # Recursion is last operation

# Can be converted to iteration:
def factorial_iterative(n):
    accumulator = 1
    while n > 1:
        accumulator *= n
        n -= 1
    return accumulator

Practice Problems

Here are recommended problems to practice recursion and divide-and-conquer:

Easy

• LeetCode 70: Climbing Stairs
• LeetCode 509: Fibonacci Number
• LeetCode 344: Reverse String
• LeetCode 206: Reverse Linked List
• LeetCode 104: Maximum Depth of Binary Tree

Medium

• LeetCode 50: Pow(x, n)
• LeetCode 46: Permutations
• LeetCode 78: Subsets
• LeetCode 22: Generate Parentheses
• LeetCode 53: Maximum Subarray
• LeetCode 240: Search a 2D Matrix II

Hard

• LeetCode 51: N-Queens
• LeetCode 23: Merge k Sorted Lists
• LeetCode 315: Count of Smaller Numbers After Self
• LeetCode 327: Count of Range Sum

Key Concepts to Practice

• Identifying base cases and recursive cases
• Understanding the call stack
• Implementing memoization
• Converting between recursive and iterative solutions
• Debugging recursive functions

Summary

Recursion and divide-and-conquer are fundamental techniques in computer science. Recursion provides an elegant way to solve problems with natural recursive structure, while divide-and-conquer enables efficient solutions by breaking problems into smaller subproblems. Memoization optimizes recursive solutions by eliminating redundant computations.

Key takeaways:

• Every recursive function needs a base case and recursive case
• Divide-and-conquer follows: Divide → Conquer → Combine
• Memoization transforms exponential time complexity to polynomial
• Understanding common patterns helps recognize when to use recursion
• Practice converting between recursive and iterative solutions

These concepts form the foundation for more advanced topics like dynamic programming, graph algorithms, and tree operations covered in later chapters.