Core Components of a Recursive Function

Every recursive function must have at least two parts:

1. Base Case: This is the condition under which the function stops calling itself. It's the simplest version of the problem that can be solved directly. Without a base case, a recursive function would call itself indefinitely, leading to a "stack overflow" error.
2. Recursive Step: This is where the function calls itself, but with a modified input that brings it closer to the base case. The function breaks the problem down into a smaller version of the same problem.

# Python: generate all subsets of a set
def generate_subsets(k, current_subset, nums):
  # Base Case: processed all numbers
  if k == len(nums):
    print(current_subset)
    return
Recursive Step 1: Don't include nums[k]
generate_subsets(k + 1, current_subset, nums)
Recursive Step 2: Include nums[k]
current_subset.append(nums[k])
generate_subsets(k + 1, current_subset, nums)
current_subset.pop() # Backtrack

The Call Stack

Behind the scenes, recursion is managed by the "call stack". When a function is called, a new "stack frame" is pushed onto the call stack. This frame contains the function's parameters and local variables. When the function returns, its frame is popped off the stack. In recursion, multiple frames for the same function are pushed onto the stack, one for each recursive call. The base case ensures that the stack eventually starts unwinding.

Recursion vs. Iteration

Any problem that can be solved recursively can also be solved iteratively (using loops).

• Recursion often leads to more elegant, readable, and concise code, especially for problems that are naturally recursive, like tree traversals or backtracking. However, it can be less efficient due to the overhead of function calls and can lead to stack overflow for very deep recursion.
• Iteration can be more performant and avoids the risk of stack overflow, but the code can sometimes be more complex and harder to reason about compared to its recursive counterpart.

Backtracking

Backtracking is a specific algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time. It's a refined form of brute-force search where we "prune" branches of the search space that we know can't lead to a solution. The subset generation code above is a simple example of backtracking.

Classic backtracking problems include N-Queens, Sudoku solvers, and generating all permutations or combinations.

Interactive Demo

To see how recursion works, try the interactive Fibonacci simulation below. Notice how many times the same subproblems are computed without memoization. Then, toggle it on to see how a simple cache dramatically prunes the call tree.