The Call Tree

To compare those calls, we need a picture of all the calls a recursion makes. The call stack, from the complexity chapter, shows a recursion as it runs: the calls in progress right now, stacked with the newest on top. But it holds only the calls still waiting. To see the whole recursion, we need a view that keeps every call, even the ones that have finished, and records which call made which.

Recall the recursive Fibonacci from the complexity chapter, where each number is the sum of the two before it:

public static int fib(int n) {
  if (n <= 1) {
    return n;                       // base case
  }
  return fib(n - 1) + fib(n - 2);   // two recursive calls
}

The complexity chapter laid out all the calls that fib(5) makes. Here is the same picture for fib(4), with each call drawn above the calls it makes:

                   fib(4)
             ┌────────┴────────┐
          fib(3)            fib(2)
       ┌─────┴─────┐       ┌───┴───┐
    fib(2)      fib(1)  fib(1)  fib(0)
   ┌───┴───┐
fib(1)  fib(0)

This picture is called the call tree.

The complexity chapter also showed the stack at its deepest moment: one chain down the left side, from the first call to the first fib(1). In the call tree, that chain is the leftmost branch. At any moment, the stack holds one path in this tree, from fib(4) down to the call that is running. When that call returns, the stack pops back to its caller, and the caller’s next call starts a different path.

One call or many

Fibonacci branched because each call makes two recursive calls. Some recursions make only one. Take the factorial from the start of the chapter and run factorial(3). Drawing each call above the call it makes, we get this:

factorial(3)
      │
factorial(2)
      │
factorial(1)
      │
factorial(0)

This call tree is a chain, because each call makes exactly one call below it. For a chain, there is only one branch, so at its deepest moment, just before factorial(0) returns, the stack holds the whole call tree:

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ factorial(0)  return 1  (running now)  ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌────────────────────────────────────────┐
        │ factorial(1)  waiting for factorial(0) │
        ├────────────────────────────────────────┤
        │ factorial(2)  waiting for factorial(1) │
        ├────────────────────────────────────────┤
        │ factorial(3)  waiting for factorial(2) │
        └────────────────────────────────────────┘

Merge sort, like Fibonacci, makes two recursive calls, one on each half. Here is its call tree for [3, 8, 5, 2]:

                    mergeSort([3, 8, 5, 2])
              ┌───────────────┴─────────────────┐
      mergeSort([3, 8])                mergeSort([5, 2])
      ┌───────┴───────┐                 ┌───────┴───────┐
mergeSort([3])   mergeSort([8])   mergeSort([5])   mergeSort([2])

The number of recursive calls a method can make determines the number of branches coming out of a call in its tree. The maze search tries up to four moves, so a call there can have up to four branches.