Recursion

Recursion is a technique where a function calls itself to solve smaller subproblems. It’s fundamental to many algorithms and data structure operations.

How Recursion Works

Every recursive function has two essential parts:

1. Base Case: Condition to stop recursion
2. Recursive Case: Function calls itself with smaller input

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

# Call stack for factorial(4):
# factorial(4) → 4 * factorial(3)
#                    → 3 * factorial(2)
#                          → 2 * factorial(1)
#                                → returns 1
#                          → returns 2 * 1 = 2
#                    → returns 3 * 2 = 6
#              → returns 4 * 6 = 24

Call Stack Visualization

factorial(4)
┌─────────────────┐
│ n = 4           │
│ return 4 * ?    │ ─── calls factorial(3)
└─────────────────┘
        ↓
┌─────────────────┐
│ n = 3           │
│ return 3 * ?    │ ─── calls factorial(2)
└─────────────────┘
        ↓
┌─────────────────┐
│ n = 2           │
│ return 2 * ?    │ ─── calls factorial(1)
└─────────────────┘
        ↓
┌─────────────────┐
│ n = 1           │
│ return 1        │ ─── base case!
└─────────────────┘
        ↑
    Stack unwinds: 1 → 2 → 6 → 24

Time & Space Complexity

Factor	Description
Time	Number of recursive calls × work per call
Space	Maximum depth of call stack

# O(n) time, O(n) space
def factorial(n):
    if n <= 1: return 1
    return n * factorial(n - 1)

# O(2^n) time, O(n) space (exponential!)
def fib_naive(n):
    if n <= 1: return n
    return fib_naive(n - 1) + fib_naive(n - 2)

Common Patterns

1. Linear Recursion

Process one element at a time.

Python

def sum_array(arr, i=0):
    """Sum all elements in array"""
    if i >= len(arr):  # Base case
        return 0
    return arr[i] + sum_array(arr, i + 1)

def reverse_string(s):
    """Reverse a string"""
    if len(s) <= 1:  # Base case
        return s
    return s[-1] + reverse_string(s[:-1])

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

JavaScript

function sumArray(arr, i = 0) {
  if (i >= arr.length) return 0;
  return arr[i] + sumArray(arr, i + 1);
}

function reverseString(s) {
  if (s.length <= 1) return s;
  return s[s.length - 1] + reverseString(s.slice(0, -1));
}

function power(base, exp) {
  if (exp === 0) return 1;
  return base * power(base, exp - 1);
}

Java

public static int sumArray(int[] arr, int i) {
    if (i >= arr.length) return 0;
    return arr[i] + sumArray(arr, i + 1);
}

public static String reverseString(String s) {
    if (s.length() <= 1) return s;
    return s.charAt(s.length() - 1) + reverseString(s.substring(0, s.length() - 1));
}

public static int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

C++

int sumArray(vector<int>& arr, int i = 0) {
    if (i >= arr.size()) return 0;
    return arr[i] + sumArray(arr, i + 1);
}

string reverseString(string s) {
    if (s.length() <= 1) return s;
    return s.back() + reverseString(s.substr(0, s.length() - 1));
}

int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

2. Binary Recursion (Divide and Conquer)

Split problem in half at each step.

def binary_search(arr, target, left, right):
    """
    Binary search using recursion.
    Time: O(log n), Space: O(log n)
    """
    if left > right:
        return -1

    mid = left + (right - left) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)
    else:
        return binary_search(arr, target, left, mid - 1)

def merge_sort(arr):
    """
    Merge sort using recursion.
    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 power_optimized(base, exp):
    """
    Fast exponentiation.
    Time: O(log n), Space: O(log n)
    """
    if exp == 0:
        return 1
    if exp % 2 == 0:
        half = power_optimized(base, exp // 2)
        return half * half
    else:
        return base * power_optimized(base, exp - 1)

3. Tree Recursion

Problems that branch into multiple recursive calls.

def fibonacci(n, memo=None):
    """
    Fibonacci with memoization.
    Time: O(n), Space: O(n)
    """
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

def count_paths(m, n):
    """
    Count paths in m x n grid (only right or down).
    Time: O(2^(m+n)) without memo, O(m*n) with memo
    """
    if m == 1 or n == 1:
        return 1
    return count_paths(m - 1, n) + count_paths(m, n - 1)

4. Tree Traversal

Natural fit for recursive solutions.

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

def max_depth(root):
    """Find maximum depth of binary tree"""
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def inorder(root, result=None):
    """Inorder traversal: left, root, right"""
    if result is None:
        result = []
    if root:
        inorder(root.left, result)
        result.append(root.val)
        inorder(root.right, result)
    return result

def is_same_tree(p, q):
    """Check if two trees are identical"""
    if not p and not q:
        return True
    if not p or not q:
        return False
    return (p.val == q.val and
            is_same_tree(p.left, q.left) and
            is_same_tree(p.right, q.right))

5. Linked List Recursion

def reverse_list(head):
    """
    Reverse linked list recursively.
    Time: O(n), Space: O(n)
    """
    if not head or not head.next:
        return head

    new_head = reverse_list(head.next)
    head.next.next = head
    head.next = None

    return new_head

def merge_two_lists(l1, l2):
    """Merge two sorted linked lists"""
    if not l1:
        return l2
    if not l2:
        return l1

    if l1.val <= l2.val:
        l1.next = merge_two_lists(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_lists(l1, l2.next)
        return l2

Tail Recursion

When the recursive call is the last operation, compilers can optimize to avoid stack growth.

# Not tail recursive (multiplication happens after recursive call)
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# Tail recursive (using accumulator)
def factorial_tail(n, accumulator=1):
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)

Recursion vs Iteration

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

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

Aspect	Recursion	Iteration
Readability	Often cleaner	Can be complex
Space	O(n) stack	O(1) typically
Performance	Function call overhead	Usually faster
Use case	Trees, divide-conquer	Simple loops

Common Pitfalls

1. Missing Base Case

# Bug: Infinite recursion!
def bad_countdown(n):
    print(n)
    bad_countdown(n - 1)  # Never stops

# Fixed
def countdown(n):
    if n <= 0:  # Base case
        return
    print(n)
    countdown(n - 1)

2. Stack Overflow

# Will crash for large n
def deep_recursion(n):
    if n <= 0:
        return 0
    return 1 + deep_recursion(n - 1)

# deep_recursion(10000)  # RecursionError!

# Solution: Convert to iteration or use tail recursion
import sys
sys.setrecursionlimit(20000)  # Not recommended

3. Redundant Computation

# Exponential time - computes same values repeatedly
def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

# With memoization - linear time
def fib_fast(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_fast(n - 1, memo) + fib_fast(n - 2, memo)
    return memo[n]

Practice Problems

Easy

Problem	Pattern	Companies
Fibonacci Number	Memoization	Amazon
Reverse String	Linear	Amazon, Google
Power of Two	Divide	Amazon
Maximum Depth of Binary Tree	Tree	Amazon, Google

Medium

Problem	Pattern	Companies
Pow(x, n)	Divide and Conquer	Amazon, Meta
Generate Parentheses	Backtracking	Amazon, Google
Flatten Binary Tree	Tree	Meta, Microsoft
Decode Ways	Memoization	Amazon, Meta

Hard

Problem	Pattern	Companies
Regular Expression Matching	Backtracking	Google, Meta
Merge K Sorted Lists	Divide and Conquer	Amazon, Google
Serialize and Deserialize Binary Tree	Tree	Meta, Google

Key Takeaways

1. Always define base case - Prevents infinite recursion
2. Reduce problem size - Each call should work on smaller input
3. Trust the recursion - Assume recursive calls work correctly
4. Watch for redundancy - Use memoization when needed
5. Consider stack space - Deep recursion can overflow

Next Steps

Backtracking Use recursion for exhaustive search with pruning

Dynamic Programming Optimize recursive solutions with memoization