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

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:])

# 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

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:
def 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)

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 provides a way to determine the time complexity of divide-and-conquer algorithms. For a recurrence of the form:

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

where a ≥ 1, b > 1, and f(n) is asymptotically positive, the Master Theorem helps determine the complexity based on the relationship between f(n) and n^log_ba.

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
    mid = (left + right) // 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 (Kadane's Algorithm with Divide-and-Conquer)

Find the contiguous subarray with the largest sum. This can be solved using divide-and-conquer by finding the maximum subarray in the left half, right half, and crossing the middle.

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)

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)
memo = {}
def fibonacci(n):
    # 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) + fibonacci(n - 2)
    return memo[n]
# Time Complexity: O(n) - linear!
# Space Complexity: O(n)

Using Python's functools.lru_cache

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

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# The decorator automatically handles memoization
# maxsize=None means unlimited cache size

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.

memo = {}
def climb_stairs(n):
    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) + climb_stairs(n - 2)
    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.

memo = {}
def unique_paths(m, n):
    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) + unique_paths(m, n - 1)
    return memo[key]

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

Longest Common Subsequence

memo = {}
def lcs(s1, s2, i=0, j=0):
    key = (i, j)
    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)
    else:
        # Try both possibilities
        result = max(lcs(s1, s2, i + 1, j), lcs(s1, s2, i, j + 1))
    
    memo[key] = result
    return result

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 Chapter 8: 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)

See Chapter 7: Graph Algorithms and Chapter 4: 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
def permute(nums):
    result = []
    
    def backtrack(current):
        # Base case: permutation complete
        if len(current) == len(nums):
            result.append(current[:])
            return
        
        # Try each remaining number
        for num in nums:
            if num not in current:
                current.append(num)      # Make choice
                backtrack(current)       # Recurse
                current.pop()            # Undo choice (backtrack)
    
    backtrack([])
    return result

# 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
memo = {}
def coin_change(coins, amount):
    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)
        if result != float('inf'):
            min_coins = min(min_coins, 1 + result)
    
    memo[amount] = min_coins
    return min_coins

See Chapter 8: 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
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
memo = {}
def catalan(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return 1
    result = 0
    for i in range(n):
        result += catalan(i) * catalan(n - 1 - i)
    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.