Types of recursion, and the order a call tree is walked

Recursive functions come in a few shapes, and the shape decides how much time and memory they need. The useful way to see any recursion is its call tree: each call is a node, and the calls it makes are its children. Running the function walks that tree depth-first — all the way down the first branch, back up, then down the next.

The call tree of fib(4). fib(4) calls fib(3) and fib(2); fib(3) calls fib(2) and fib(1); each fib(2) calls fib(1) and fib(0). The small numbers show the order the calls run: depth-first, left before right, 1 to 9. The green numbers are the values each call returns. fib(2) is computed twice — the waste dynamic programming removes.

The kinds of recursion

Linear recursion — each call makes one recursive call: factorial, sum of a list, reversing a string. The call tree is a single path: n calls, depth n.
Tail recursion — linear recursion where the call is the last thing the function does, carrying the answer in a parameter. Could run in O(1) space, but JavaScript, Python and Java don't optimise it.
Tree (multiple) recursion — each call makes two or more calls: Fibonacci, generating subsets, most backtracking. The tree branches, so calls grow exponentially — b^depth for b branches — while memory is still just the depth.
Divide and conquer — split the input into parts, solve each part recursively, combine: merge sort, quick sort, binary search, fast power. Halving each time keeps the depth to log n.
Mutual recursion — two functions that call each other, like isEven(n) calling isOdd(n − 1). Parsers for nested expressions work this way.

The order the call tree is walked

Every call tree is walked depth-first. What changes is when a call does its own work relative to its recursive calls — exactly like pre-order and post-order traversals of a binary tree:

Work before the call (pre-order, "head") — the work happens on the way down, so it comes out in calling order.
Work after the call (post-order) — the work waits until the call returns, so it happens on the way back up, in reverse order. Combining children's answers (fib, merge sort, tree heights) is always post-order.

The same function prints 3, 2, 1 or 1, 2, 3 depending only on where the line sits:

1function countDown(n, out = []) {2  if (n === 0) return out;3  out.push(n);                    // work before the call: comes out first4  return countDown(n - 1, out);5}

JavaScript5 lines

1function countUp(n, out = []) {2  if (n === 0) return out;3  countUp(n - 1, out);            // the call first ...4  out.push(n);                    // ... then the work: comes out last5  return out;6}

JavaScript6 lines

Tree recursion in action

Dry-run simulator

fib(n): the call tree

Watch the call tree grow depth-first, and notice the same small calls being solved again and again.

1function fib(n) {2  if (n <= 1) return n;                  // base cases: fib(0) = 0, fib(1) = 13  return fib(n - 1) + fib(n - 2);        // two calls: the call tree branches4}

JavaScript4 lines

Time and memory at a glance

shape                   example          calls (time)        depth (stack memory)
linear                  factorial(n)     n                   n
tree, 2 branches        fib(n)           about 1.6^n         n
divide and conquer      merge sort       about 2n            log n
halving, one branch     binary search    log n               log n
backtracking            subsets of n     2^n                 n

Two rules cover almost everything: time ≈ number of calls × work per call, and space ≈ maximum depth × memory per frame (plus anything you store).

Key takeaways

Draw the call tree: its size is the time, its height is the stack memory.
Linear recursion is a path; tree recursion branches and grows exponentially; divide and conquer stays log n deep.
The tree is always walked depth-first; work before the calls happens top-down, work after happens bottom-up.
Repeated subtrees, like fib(2) above, are the signal for dynamic programming.

Prev Next

Was this helpful?