Learn what recursion is, how the call stack works, and how to think recursively.

Recursion

Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive solution has two parts — a base case that stops the recursion, and a recursive case that breaks the problem down and calls the function again.

Think of recursion like Russian nesting dolls. To open the outermost doll, you find a smaller one inside. To open that one, you find an even smaller one. You keep going until you reach the smallest doll — the base case — which has nothing inside. Then you work back out.

Call Stackfactorial(5) — stack grows then unwinds

call stack

stack empty

stack bottom

return values

factorial(1) = ?

factorial(2) = ?

factorial(3) = ?

factorial(4) = ?

factorial(5) = ?

factorial.py

def factorial(n):

# base case

if n == 0: return 1

return n * factorial(n - 1)

# all frames resolved

Call factorial(5)

step 0/12

The two required parts

def factorial(n):
    # base case — stop here, no more recursion
    if n == 0:
        return 1

    # recursive case — call itself with a smaller input
    return n * factorial(n - 1)

Without the base case, the function calls itself forever — a RecursionError. Without the recursive case, the function never reduces the problem and just returns the base case immediately.

How the call stack works

Every function call adds a frame to the call stack — a record of the function's local variables and where to return to when it finishes. With recursion, frames stack up until the base case is reached, then unwind one by one.

factorial(4)
  calls factorial(3)
    calls factorial(2)
      calls factorial(1)
        calls factorial(0)
          returns 1         ← base case reached
        returns 1 × 1 = 1
      returns 2 × 1 = 2
    returns 3 × 2 = 6
  returns 4 × 6 = 24

The visual above shows this stack growing and shrinking in real time.

Three steps to write a recursive function

Step 1 — identify the base case. What is the simplest possible input? Factorial of 0 is 1. An empty list reversed is still an empty list. A single node's height is 0.

Step 2 — identify the recursive case. How does a solution for input n relate to a solution for input n-1? Factorial of n is n × factorial(n-1). The sum of a list is list[0] + sum(list[1:]).

Step 3 — trust the recursion. Assume the recursive call returns the correct answer for the smaller input. Your job is only to combine that answer with the current level's contribution.

Common recursive patterns

# pattern 1 — reduce by 1
def count_down(n):
    if n == 0: return
    print(n)
    count_down(n - 1)

# pattern 2 — reduce by half (faster)
def binary_search(arr, target, lo, hi):
    if lo > hi: return -1
    mid = (lo + hi) // 2
    if arr[mid] == target: return mid
    if arr[mid] < target: return binary_search(arr, target, mid+1, hi)
    return binary_search(arr, target, lo, mid-1)

# pattern 3 — tree shape (two recursive calls)
def fibonacci(n):
    if n <= 1: return n
    return fibonacci(n-1) + fibonacci(n-2)

Recursion vs iteration

Any recursive function can be rewritten as a loop — and vice versa. The choice depends on clarity and constraints:

	Recursion	Iteration
Code clarity	Often cleaner for tree/graph problems	Cleaner for simple loops
Memory	O(depth) call stack	O(1) typically
Risk	Stack overflow on deep inputs	No stack limit
Natural fit	Trees, graphs, divide and conquer	Arrays, simple counting

Python's default recursion limit is 1000 calls deep. For problems where depth could exceed this — like processing a linked list with 10,000 nodes recursively — use an iterative approach or increase the limit with sys.setrecursionlimit().

When recursion is the natural choice

Recursion shines when the problem has a recursive structure — where the solution is naturally defined in terms of solutions to smaller sub-problems:

Trees and graphs — process a node and recursively process its children
Divide and conquer — split the problem, solve each half, combine
Backtracking — explore all paths, undoing choices when they fail
Mathematical definitions — factorial, Fibonacci, Ackermann function
Nested structures — flatten a nested list, evaluate a parse tree

Recursion — Introduction