Recursion

coreCommon atGoogleMetaAmazonAnthropicRead firstStacksComplexity analysisPractise in the Sandbox →

A recursive function handles a base case directly and otherwise calls itself on a smaller input, then combines the result. Each pending call is a frame on the call stack, so space is O(max depth). Time is (number of calls) × (work per call): count the nodes of the call tree.

The idea in plain words

You’re in a queue at a cinema and want to know your position. You can’t see the front. So you ask the person ahead: “what’s your position?” They ask the person ahead of them, and so on. The person at the front knows they’re number 1 (the base case). The answer travels back: 1, 2, 3… each person adds one and passes it on.

Three things make that work, and every correct recursive function has them:

• A base case that answers without asking anyone.
• Progress: each question goes to someone strictly closer to the base case.
• A combine step done after the answer comes back (“add one”).

While you wait for the answer, you’re paused, holding your own state. That paused state is a stack frame. A computer keeps one frame per pending call, stacked in the order they were made. The most recent call finishes first: last in, first out.

The leap of faith

When writing the recursive case, assume the recursive call already works for the smaller input, and only ask: “given that answer, how do I finish mine?” Don’t trace the whole chain in your head. Check the base case and the progress, and the rest follows by induction.

See it

Pick a function and step through. The left side is the call stack: the top frame is running, the ones below are paused, each showing what it’s waiting for. The right side is the call tree: every call ever made. Try naive fib(5) and watch the same calls get recomputed (amber).

Call stack and call tree

step through

n (0–6)

call stack (top first)

fib(4)

running: fib(3) + fib(2) = ? + ?

eventpush

depth1

max depth1

calls so far1

just calledon the stack (paused)returnedrepeat of an earlier call

The first call. A new frame is pushed (depth 1); it holds this call's own copy of its argument.

↺◀▶ Play▶1 / 18

Notice the two different numbers. Max depth (the tallest the stack gets) decides memory. Calls so far (the size of the tree) decides time. For power the tree is a thin chain of length log n. For naive fib it’s a bushy tree of about 1.6ⁿ calls, but its depth is still only n.

When to reach for it

The problem says…	Why recursion fits
a tree, nested structure, or anything defined in terms of itself	The code mirrors the definition: handle this node, recurse on the children.
“all subsets / permutations / combinations”	Each call makes one choice, then recurses on the rest. See backtracking.
a problem that splits into independent halves	Divide and conquer: merge sort, fast power.
“number of ways”, “best value” over overlapping subproblems	Recursion first, then add memoization.
graph exploration, “visit everything reachable”	Depth-first search is recursion plus a visited set.

How it works

1. Base case. The smallest input(s), answered directly. Put it first in the function.
2. Recursive case. Call yourself on an input that is strictly smaller (shorter list, smaller n, a child node).
3. Combine. Use the returned value to build this call’s answer, then return it.

Python

basics.py

def factorial(n: int) -> int:
    """n! = n * (n-1)!, with 0! = 1."""
    if n < 0:
        raise ValueError("n must be >= 0")
    if n == 0:                      # 1. base case: answer known without recursing
        return 1
    return n * factorial(n - 1)     # 2. smaller subproblem, 3. combine on the way back


def total(xs: list[int], i: int = 0) -> int:
    """Sum of xs[i:]. Passing an index avoids copying a slice at every level (O(n^2))."""
    if i == len(xs):                # 1. base case: an empty suffix sums to 0
        return 0
    return xs[i] + total(xs, i + 1) # 2. shrink by one element, 3. add it back


if __name__ == "__main__":
    assert [factorial(n) for n in range(6)] == [1, 1, 2, 6, 24, 120]
    assert factorial(20) == 2_432_902_008_176_640_000
    assert total([4, 8, 15, 16, 23, 42]) == 108
    assert total([]) == 0
    print("ok")

TypeScript

basics.ts

import assert from "node:assert/strict";

/** n! = n * (n-1)!, with 0! = 1. bigint because 21! is past 2^53. */
export function factorial(n: number): bigint {
  if (n < 0) throw new RangeError("n must be >= 0");
  if (n === 0) return 1n; // 1. base case: answer known without recursing
  return BigInt(n) * factorial(n - 1); // 2. smaller subproblem, 3. combine on the way back
}

/** Sum of xs[i..]. Passing an index avoids copying a slice at every level (O(n^2)). */
export function total(xs: number[], i = 0): number {
  if (i === xs.length) return 0; // 1. base case: an empty suffix sums to 0
  return xs[i] + total(xs, i + 1); // 2. shrink by one element, 3. add it back
}

assert.deepEqual([0, 1, 2, 3, 4, 5].map(factorial), [1n, 1n, 2n, 6n, 24n, 120n]);
assert.equal(factorial(20), 2_432_902_008_176_640_000n);
assert.equal(total([4, 8, 15, 16, 23, 42]), 108);
assert.equal(total([]), 0);
console.log("ok");

C#

basics.cs

// n! = n * (n-1)!, with 0! = 1. long holds up to 20!.
static long Factorial(int n)
{
    if (n < 0) throw new ArgumentOutOfRangeException(nameof(n));
    if (n == 0) return 1;              // 1. base case: answer known without recursing
    return n * Factorial(n - 1);       // 2. smaller subproblem, 3. combine on the way back
}

// Sum of xs[i..]. A span slice is free (no copy), unlike slicing a list.
static long Total(ReadOnlySpan<int> xs)
{
    if (xs.IsEmpty) return 0;          // 1. base case: an empty suffix sums to 0
    return xs[0] + Total(xs[1..]);     // 2. shrink by one element, 3. add it back
}

if (Factorial(5) != 120) throw new Exception("5!");
if (Factorial(20) != 2_432_902_008_176_640_000) throw new Exception("20!");
if (Total([4, 8, 15, 16, 23, 42]) != 108) throw new Exception("total");
if (Total([]) != 0) throw new Exception("empty");
Console.WriteLine("ok");

The choice of how to shrink the input changes the cost completely. Going from n to n − 1 makes n calls. Going from n to n / 2 makes only log₂ n:

Python

power.py

def power(x: int, n: int) -> int:
    """x ** n in O(log n) multiplications, by halving n."""
    if n < 0:
        raise ValueError("n must be >= 0")
    if n == 0:                       # 1. base case
        return 1
    half = power(x, n // 2)          # 2. ONE recursive call, on a problem half the size
    if n % 2 == 0:
        return half * half           # 3. x^n = (x^(n/2))^2
    return half * half * x           #    odd n: one extra factor of x


if __name__ == "__main__":
    assert power(2, 10) == 1024
    assert power(3, 0) == 1
    assert power(-2, 5) == -32
    assert power(7, 13) == 7**13
    assert power(2, 1000) == 2**1000   # depth is only ~10, not 1000
    print("ok")

TypeScript

power.ts

import assert from "node:assert/strict";

/** x ** n in O(log n) multiplications, by halving n. */
export function power(x: bigint, n: number): bigint {
  if (n < 0) throw new RangeError("n must be >= 0");
  if (n === 0) return 1n; // 1. base case
  const half = power(x, Math.floor(n / 2)); // 2. ONE recursive call, on half the problem
  return n % 2 === 0
    ? half * half // 3. x^n = (x^(n/2))^2
    : half * half * x; //    odd n: one extra factor of x
}

assert.equal(power(2n, 10), 1024n);
assert.equal(power(3n, 0), 1n);
assert.equal(power(-2n, 5), -32n);
assert.equal(power(7n, 13), 7n ** 13n);
assert.equal(power(2n, 1000), 2n ** 1000n); // depth is only ~10, not 1000
console.log("ok");

C#

power.cs

using System.Numerics;

// x^n in O(log n) multiplications, by halving n.
static BigInteger Power(BigInteger x, int n)
{
    if (n < 0) throw new ArgumentOutOfRangeException(nameof(n));
    if (n == 0) return 1;                    // 1. base case
    var half = Power(x, n / 2);              // 2. ONE recursive call, on half the problem
    return n % 2 == 0
        ? half * half                        // 3. x^n = (x^(n/2))^2
        : half * half * x;                   //    odd n: one extra factor of x
}

if (Power(2, 10) != 1024) throw new Exception("2^10");
if (Power(3, 0) != 1) throw new Exception("3^0");
if (Power(-2, 5) != -32) throw new Exception("(-2)^5");
if (Power(2, 1000) != BigInteger.Pow(2, 1000)) throw new Exception("2^1000"); // depth ~10
Console.WriteLine("ok");

Call once, reuse the result

Writing power(x, n // 2) * power(x, n // 2) looks harmless, but it makes two calls per level. The tree doubles at each of log n levels, so it does 2^(log n) = n calls: back to O(n). Store the half in a variable.

Replacing recursion with an explicit stack

Deep recursion can overflow the call stack. Any recursive function can be rewritten with your own stack, because that’s all the machine is doing anyway:

1. Push the initial arguments as a “frame”.
2. Loop: pop a frame. That’s starting a call. Handle the base case and continue.
3. Push frames for the “recursive calls”. If you need to combine results after children finish, push a marker meaning “come back to me”, or process in post-order.

Python

to_stack.py

from dataclasses import dataclass


@dataclass
class Node:
    val: int
    left: "Node | None" = None
    right: "Node | None" = None


def depth_recursive(node: Node | None) -> int:
    if node is None:
        return 0
    return 1 + max(depth_recursive(node.left), depth_recursive(node.right))


def depth_iterative(root: Node | None) -> int:
    """Same answer with an explicit stack: no recursion limit, depth bounded by memory."""
    best = 0
    stack = [(root, 1)]                 # 1. each entry is a "frame": the args of one call
    while stack:
        node, d = stack.pop()           # 2. pop = start running that call
        if node is None:
            continue                    #    base case
        best = max(best, d)
        stack.append((node.left, d + 1))   # 3. push = make a recursive call
        stack.append((node.right, d + 1))
    return best


if __name__ == "__main__":
    tree = Node(1, Node(2, Node(4)), Node(3, None, Node(5, Node(6))))
    assert depth_recursive(tree) == depth_iterative(tree) == 4
    chain: Node | None = None
    for i in range(100_000):            # a 100k-deep "tree" (a linked list)
        chain = Node(i, chain)
    assert depth_iterative(chain) == 100_000   # depth_recursive would hit RecursionError
    print("ok")

TypeScript

to_stack.ts

import assert from "node:assert/strict";

interface TreeNode { val: number; left: TreeNode | null; right: TreeNode | null }
const node = (val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode => ({ val, left, right });

export function depthRecursive(n: TreeNode | null): number {
  if (n === null) return 0;
  return 1 + Math.max(depthRecursive(n.left), depthRecursive(n.right));
}

/** Same answer with an explicit stack: no call-stack limit, depth bounded by memory. */
export function depthIterative(root: TreeNode | null): number {
  let best = 0;
  const stack: [TreeNode | null, number][] = [[root, 1]]; // 1. each entry is one call's args
  while (stack.length > 0) {
    const [n, d] = stack.pop()!; // 2. pop = start running that call
    if (n === null) continue; //    base case
    best = Math.max(best, d);
    stack.push([n.left, d + 1], [n.right, d + 1]); // 3. push = make a recursive call
  }
  return best;
}

const tree = node(1, node(2, node(4)), node(3, null, node(5, node(6))));
assert.equal(depthRecursive(tree), 4);
assert.equal(depthIterative(tree), 4);
let chain: TreeNode | null = null;
for (let i = 0; i < 100_000; i++) chain = node(i, chain); // 100k deep
assert.equal(depthIterative(chain), 100_000); // the recursive one would throw RangeError
console.log("ok");

C#

to_stack.cs

var tree = new Node(1, new Node(2, new Node(4)), new Node(3, null, new Node(5, new Node(6))));
if (DepthRecursive(tree) != 4 || DepthIterative(tree) != 4) throw new Exception("depth 4");
Node? chain = null;
for (int i = 0; i < 100_000; i++) chain = new Node(i, chain);   // 100k deep
// The recursive version could crash the process here: StackOverflowException can't be caught.
if (DepthIterative(chain) != 100_000) throw new Exception("deep chain");
Console.WriteLine("ok");

static int DepthRecursive(Node? n) =>
    n is null ? 0 : 1 + Math.Max(DepthRecursive(n.Left), DepthRecursive(n.Right));

// Same answer with an explicit stack: no call-stack limit, depth bounded by memory.
static int DepthIterative(Node? root)
{
    int best = 0;
    var stack = new Stack<(Node? Node, int Depth)>();
    stack.Push((root, 1));                       // 1. each entry is one call's args
    while (stack.Count > 0)
    {
        var (n, d) = stack.Pop();                // 2. pop = start running that call
        if (n is null) continue;                 //    base case
        best = Math.Max(best, d);
        stack.Push((n.Left, d + 1));             // 3. push = make a recursive call
        stack.Push((n.Right, d + 1));
    }
    return best;
}

record Node(int Val, Node? Left = null, Node? Right = null);

What it costs

Shape of the recursion	Calls (time)	Max depth (space)	Example
one call, n → n − 1	O(n)	O(n)	factorial, sum of a list
one call, n → n / 2	O(log n)	O(log n)	fast power, recursive binary search
two calls, n → n / 2, O(n) combine	O(n log n)	O(log n)	merge sort
two calls, n → n − 1 and n − 2	O(φⁿ) ≈ O(1.618ⁿ)	O(n)	naive Fibonacci
two calls, n → n − 1	O(2ⁿ)	O(n)	generate all subsets
one call per child of a tree	O(nodes)	O(height)	tree depth, tree sum

Time = total calls × work done inside one call (excluding the recursive calls). Draw the call tree and add it up level by level; divide and conquer turns that into the master theorem.

Space = max depth × frame size, plus anything you allocate. That’s why a balanced tree costs O(log n) stack but a degenerate one (a linked list in disguise) costs O(n).

Hidden costs. Slicing (xs[1:] in Python, xs.slice(1) in TS) copies the list at every level, turning an O(n) recursion into O(n²) time and space. Pass an index instead. C#’s Span<T> slicing is free, which is why the C# sample uses it.

Stack limits, per language

	Default limit	When you exceed it
Python	sys.getrecursionlimit() is 1000 frames by default	RecursionError (catchable). sys.setrecursionlimit raises the limit, but the real C stack can still crash the process.
JavaScript (V8 / Node)	depends on stack size and frame size: roughly 10k frames	RangeError: Maximum call stack size exceeded (catchable).
C# / .NET	1 MB main-thread stack on Windows, typically 8 MB on Linux and macOS: tens of thousands of small frames	StackOverflowException. It cannot be caught: the process is terminated.

None of the three does tail-call optimization you can rely on. CPython deliberately doesn’t. The ES2015 spec includes proper tail calls, but V8 (Node, Chrome) never shipped them. The .NET JIT sometimes emits tail calls, but C# doesn’t guarantee it. So “make it tail recursive” is not a fix in these languages: convert to a loop or an explicit stack.

Variations you’ll meet

• Multiple recursion. Two or more calls per frame (trees, Fibonacci, subsets). Count the tree, not the depth.
• Recursion with accumulators. Pass a running result down (total(xs, i, acc)) instead of combining on the way up. Fine for clarity; not faster without tail-call optimization.
• Mutual recursion. is_even calls is_odd calls is_even. Common in recursive-descent parsers: expression calls term calls factor calls expression.
• Recursion over structure. Trees and nested data. The base case is the empty tree or a leaf; recursion follows the children.
• Memoized recursion. Cache results by argument. Naive fib drops from O(1.6ⁿ) to O(n). See memoization.
• Backtracking. Recursion that makes a choice, recurses, then undoes the choice. See backtracking.

Pitfalls

• Missing or unreachable base case. factorial(-1) never reaches 0. Validate input or make the base case n <= 0.
• Not making progress. Recursing on the same size (f(n) calls f(n)), or on a size that doesn’t shrink for some inputs.
• Accidental exponential time. Calling the same subproblem twice per frame (see the caution above), or overlapping subproblems without a cache.
• Copying at every level. Slices, string concatenation, copying a set per call. Quietly adds a factor of n.
• Shared mutable state. Appending to one list from many calls without removing what you added. That’s the backtracking bug.
• Depth on adversarial input. Recursive DFS on a 10⁵-node path graph blows the stack in all three languages. Mention it, and offer the explicit-stack version.
• Mutable default arguments in Python. def f(x, seen=set()) shares one set across all top-level calls. Use None and create it inside.

In the interview

• Say the three parts out loud before coding: “Base case: empty list returns 0. Recursive case: first element plus the sum of the rest. It always shrinks by one.”
• State both costs: “n calls, O(1) each, so O(n) time; depth n, so O(n) stack.” Interviewers often check whether you remember the stack.
• Ask about input size. If depth could reach 10⁴ or more, say so and either propose the iterative version or ask whether recursion is acceptable.
• If you see the same arguments twice in your call tree, say: “These subproblems overlap, so I’d memoize.”
• Likely follow-ups: “What’s the space complexity?”, “What if the input is a million deep?”, “Can you do it iteratively?”, “Can you avoid recomputing?”

Check yourself

Check yourself

pick one

A recursive function walks a binary tree with n nodes, doing O(1) work per node. The tree is a straight line (every node has only a right child). What are the time and stack space?

AO(n) time, O(log n) spaceBO(n) time, O(n) spaceCO(log n) time, O(log n) spaceDO(n log n) time, O(n) space

Check yourself

pick one

power(x, n) is written as: if n == 0 return 1; return power(x, n/2) * power(x, n/2) * (n odd ? x : 1). How many calls does it make?

AO(log n), because n halves each timeBO(n), because each level doubles the number of callsCO(n log n)DO(2ⁿ)

Check yourself

pick one

Your recursive DFS works in Python on small tests but the real graph is a path of 200,000 nodes. What is the most reliable fix?

AMake the function tail-recursiveBCall sys.setrecursionlimit(10**6)CRewrite it with an explicit stack (a list used as a stack)DUse @functools.cache

Practice on your own

These are classic textbook exercises, not gym questions:

• Reverse a string, and check whether one is a palindrome, recursively.
• Towers of Hanoi: print the moves for n disks. How many moves, and what’s the max depth?
• Sum the digits of a non-negative integer until a single digit remains.
• Flatten a binary tree into its in-order list, then do it again with an explicit stack.
• Count the paths from the top-left to the bottom-right of an R × C grid moving only right or down. Then add a cache and compare the call counts.

Go deeper

• Structure and Interpretation of Computer Programs (Abelson and Sussman), section 1.2, “Procedures and the Processes They Generate”: linear vs tree recursion, with Fibonacci and fast exponentiation.
• Python docs: sys.setrecursionlimit, including the warning that a too-high limit can crash the interpreter.
• .NET docs: StackOverflowException: why it can’t be caught and how to avoid deep recursion.
• CLRS (Introduction to Algorithms), ch. 4: recurrences and the recursion-tree method for counting the cost of recursive algorithms.

Related

Divide and conquerRecursion that splits in halves, and the master theorem for its cost.

MemoizationCache repeated calls: exponential becomes polynomial.

BacktrackingRecursion that tries a choice, recurses, then undoes it.

Depth-first searchRecursion on graphs, and its explicit-stack twin.