Recursion Explained: What It Is, How It Works, and When to Use It

Recursion is when a function calls itself to solve a smaller version of the same problem. Instead of writing a loop, you trust the function to handle the next step — as long as you define exactly when it should stop.

Every recursive solution has two parts:

1. Base case — the condition that stops the recursion (no more self-calls)
2. Recursive case — the self-call that moves closer to the base case

Miss the base case and you get infinite recursion. Miss the recursive case and nothing happens. Get both right and you unlock an elegant problem-solving pattern.

Quick reference

How the call stack works

Every function call reserves a stack frame — a slot in memory that holds local variables, parameters, and the return address. When a function calls itself recursively, a new frame is pushed on top of the stack. When it returns, that frame is popped.

Here is what the call stack looks like when you compute factorial(4):

factorial(4)            ← pushed first
  factorial(3)          ← pushed
    factorial(2)        ← pushed
      factorial(1)      ← base case: returns 1
    ← returns 1 * 1 = 1
  ← returns 2 * 1 = 2
← returns 3 * 2 = 6
← returns 4 * 6 = 24

Each indentation level is one stack frame. Most runtimes cap the stack at a few thousand frames (Python defaults to 1,000). Exceeding that limit raises a stack overflow error.

Your first recursive function: factorial

Factorial of n (written n!) is n × (n−1) × (n−2) × … × 1. The base case is factorial(0) = 1.

Python

def factorial(n: int) -> int:
    # base case
    if n == 0:
        return 1
    # recursive case
    return n * factorial(n - 1)

print(factorial(5))   # 120
print(factorial(0))   # 1

JavaScript

function factorial(n) {
  if (n === 0) return 1;          // base case
  return n * factorial(n - 1);   // recursive case
}

console.log(factorial(5));  // 120

Java

public static long factorial(int n) {
    if (n == 0) return 1;              // base case
    return n * factorial(n - 1);      // recursive case
}

System.out.println(factorial(5));  // 120

Go

func factorial(n int) int {
    if n == 0 { return 1 }          // base case
    return n * factorial(n-1)       // recursive case
}

fmt.Println(factorial(5))  // 120

Classic example 2: Fibonacci

The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13… Each number is the sum of the two before it.

def fib(n: int) -> int:
    if n <= 1:           # base cases: fib(0)=0, fib(1)=1
        return n
    return fib(n - 1) + fib(n - 2)   # recursive case

print(fib(10))   # 55

Warning: naive Fibonacci is exponentially slow — fib(50) makes over a trillion calls. Fix it with memoization (below).

Memoization: caching recursive results

Memoization stores the result of each unique call so you never solve the same subproblem twice. It turns the naïve Fibonacci from O(2ⁿ) to O(n).

Python (built-in cache)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))   # 12586269025  (instant)

JavaScript (manual cache)

const memo = {};

function fib(n) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fib(n - 1) + fib(n - 2);
  return memo[n];
}

console.log(fib(50));  // 12586269025

The memoized call graph now looks like a straight line instead of a tree — each fib(k) is computed exactly once.

Recursion vs iteration

Both solve the same problems. Choose based on clarity and constraints.

Rule of thumb: if the problem naturally decomposes into smaller identical subproblems (trees, graphs, permutations, divide-and-conquer), recursion wins on clarity. If it is a simple counter or accumulator, use a loop.

Converting recursion to iteration

Every recursive algorithm can be converted to an iterative one using an explicit stack. Here is factorial as a loop:

def factorial_iter(n: int) -> int:
    result = 1
    while n > 1:
        result *= n
        n -= 1
    return result

And Fibonacci with a loop (O(1) space):

def fib_iter(n: int) -> int:
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Tail recursion

A function is tail recursive when the recursive call is the last operation — no work happens after it returns.

# NOT tail recursive — multiplies after the recursive call returns
def factorial(n):
    if n == 0: return 1
    return n * factorial(n - 1)   # multiplication happens on the way back up

# Tail recursive — accumulator carries the result
def factorial_tail(n, acc=1):
    if n == 0: return acc
    return factorial_tail(n - 1, n * acc)   # call is the last thing

Languages like Scheme, Erlang, Elixir, and some Scala compilers can optimise tail-recursive calls into a loop (eliminating stack growth). Python and Java do NOT do this, so tail recursion in those languages still risks stack overflow on large inputs.

Divide and conquer: merge sort

Merge sort is a textbook recursion pattern: split the array in half, sort each half recursively, then merge.

def merge_sort(arr: list) -> list:
    if len(arr) <= 1:                   # base case
        return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])       # recursive case
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left: list, right: list) -> list:
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

print(merge_sort([5, 2, 8, 1, 9, 3]))  # [1, 2, 3, 5, 8, 9]

Time: O(n log n) in all cases. Space: O(n) for the temporary arrays.

Tree traversal

Trees are the most natural data structure for recursion — every node is the root of its own subtree.

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

def inorder(node):           # Left → Root → Right  (sorted for BST)
    if node is None: return
    inorder(node.left)
    print(node.val, end=" ")
    inorder(node.right)

def preorder(node):          # Root → Left → Right
    if node is None: return
    print(node.val, end=" ")
    preorder(node.left)
    preorder(node.right)

def postorder(node):         # Left → Right → Root  (delete bottom-up)
    if node is None: return
    postorder(node.left)
    postorder(node.right)
    print(node.val, end=" ")

Backtracking

Backtracking is recursive exploration with the ability to undo a choice when it leads to a dead end. The pattern:

1. Make a choice
2. Recurse
3. Undo the choice (backtrack)

All permutations of a list:

def permutations(nums: list) -> list[list]:
    result = []

    def backtrack(current, remaining):
        if not remaining:           # base case — permutation complete
            result.append(current[:])
            return
        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()           # undo choice

    backtrack([], nums)
    return result

print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Classic backtracking problems: N-Queens, Sudoku solver, generating all subsets, word search on a grid.

10 classic recursive problems

Mutual (indirect) recursion

Two functions can call each other — common when parsing grammars or checking even/odd:

def is_even(n: int) -> bool:
    if n == 0: return True
    return is_odd(n - 1)

def is_odd(n: int) -> bool:
    if n == 0: return False
    return is_even(n - 1)

print(is_even(4))   # True
print(is_odd(7))    # True

Recursion depth limits

For deep recursion, prefer iteration or an explicit stack over changing runtime limits.

Common mistakes

Recursion vs dynamic programming

Dynamic programming (DP) is memoised recursion written bottom-up. Both solve overlapping subproblems; the choice is style:

FAQ

Q: Why does Python limit recursion to 1,000 calls?
A: CPython does not optimise tail calls, and deeply recursive programs can exhaust the C stack. The limit protects against accidental infinite recursion crashing the interpreter. You can raise it with sys.setrecursionlimit(), but for large depths prefer an iterative solution.

Q: Is recursion slower than iteration?
A: Slightly — each function call has overhead (push/pop a stack frame, create local variables). For simple problems like summing an array, iteration is faster. For tree traversal or divide-and-conquer, the difference is negligible and recursion is clearer.

Q: What is the difference between recursion and a loop?
A: A loop explicitly repeats a block of code using a counter or condition. Recursion re-invokes a function with smaller input and relies on the call stack to track state. Any recursion can be converted to a loop (using an explicit stack if needed), and vice versa.

Q: When should I use recursion?
A: Use recursion when the problem has a naturally recursive structure — trees, graphs, divide-and-conquer (merge sort, binary search), combinatorics (permutations, subsets), and backtracking (Sudoku, N-Queens). Avoid it for simple sequential loops where iteration is clearer and avoids stack overhead.

Q: What causes a "maximum recursion depth exceeded" / stack overflow?
A: Either a missing base case (infinite recursion) or legitimate deep recursion that exceeds the stack limit. Debug by printing function arguments on each call to see if the problem shrinks toward the base case.

Q: How does memoisation differ from dynamic programming?
A: Memoisation (top-down DP) is recursion with a cache — you start from the top and store results as you go. Bottom-up DP fills a table starting from the smallest subproblems. Both have the same time complexity; memoisation is often easier to write, bottom-up uses less stack space.