Recursion — Explained with Examples

Recursion is a technique where a function calls itself to solve smaller instances of the same problem until reaching a base case.

Recursion requires two components: a base case that stops the recursion (e.g., n === 0) and a recursive case that calls the function with modified arguments. Each recursive call adds a frame to the call stack. Without a proper base case, recursion causes stack overflow. Tail recursion optimizes by reusing the current stack frame when the recursive call is the final operation.

Think of recursion like Russian nesting dolls (matryoshka). To open the largest doll, you open it to find a smaller doll, open that to find an even smaller one, until you reach the smallest doll (base case). Then you assemble them back in reverse order as each function returns.

Recursion shines for problems with recursive structure: tree traversal, divide-and-conquer algorithms, backtracking, and problems defined in terms of themselves. Iteration is usually more efficient for simple loops.

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

# Tree traversal with recursion
def traverse(node):
    if node is None:
        return
    print(node.value)
    traverse(node.left)   # Recursive
    traverse(node.right)  # Recursive

print(factorial(5))  # 120

Every recursive solution can be implemented iteratively using an explicit stack. Recursion trades efficiency for readability — use it when the problem naturally decomposes into self-similar subproblems.

Divide and Conquer, Dynamic Programming, DFS, Backtracking

DP with Recursion