Skip to main content

Subjects

Recursion — Solving Problems by Solving Smaller Problems

recursionalgorithmsbeginnerfree
Understand recursion from the ground up — base cases, recursive cases, the call stack, and when recursion is the right tool.
Share:

What Is Recursion?

Recursion is a function that calls itself to solve a smaller version of the same problem. It keeps calling itself until it hits a base case — a problem small enough to solve directly.

Think of Russian nesting dolls. Open the big one, there is a slightly smaller one. Open that, there is an even smaller one. Eventually you reach the smallest doll that does not open — that is your base case.

Anatomy of a Recursive Function

Every recursive function needs two things:

  1. Base case — the condition that stops recursion. Without it, you get infinite recursion and a stack overflow.
  2. Recursive case — the function calls itself with a smaller or simpler input, moving toward the base case.

If you can define a problem in terms of smaller versions of itself, recursion is a natural fit.

python
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

for i in range(1, 8):
    print(f"{i}! = {factorial(i)}")

print()

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

for i in range(10):
    print(f"fib({i}) = {fibonacci(i)}")

The Call Stack

Every recursive call pushes a new stack frame. Each frame holds its own copy of parameters and local variables. When the base case returns, frames pop off one by one, combining results as they go.

For factorial(4), the call stack looks like:

factorial(4) -> 4 * factorial(3)
  factorial(3) -> 3 * factorial(2)
    factorial(2) -> 2 * factorial(1)
      factorial(1) -> 1  (base case)
    returns 2 * 1 = 2
  returns 3 * 2 = 6
returns 4 * 6 = 24

Python’s default recursion limit is 1000 frames. For deeper recursion, use iteration or increase the limit with sys.setrecursionlimit().

When to Use Recursion

Good fit: tree/graph traversal, divide-and-conquer (merge sort, quick sort), backtracking (permutations, subsets), problems with natural self-similar structure.

Bad fit: simple iteration (summing a list), deep linear recursion (stack overflow risk), performance-critical code without memoization.

Rule of thumb: if a loop does the job clearly, use a loop. If the problem has a tree-like branching structure, recursion is usually cleaner.

Key Takeaways

  • Recursion = function calls itself with a smaller input until hitting a base case.
  • Every recursive function needs a base case (stops) and a recursive case (shrinks the problem).
  • Each call pushes a frame onto the call stack. Deep recursion can overflow it.
  • Naive recursive Fibonacci is O(2ⁿ). Memoization makes it O(n).
  • Recursion shines for trees, graphs, backtracking, and divide-and-conquer. For simple loops, just use a loop.