Recursion: Time and Space Complexity Analysis - 2

A second recursive call doubles the number of calls on every new level

Consider a function that stops at zero and otherwise makes two recursive calls with n - 1. The two calls look identical in the code, but they create separate invocations. Each invocation gets its own stack frame and creates two more calls unless it reaches the base case.

void branch(int n) {
    if (n == 0) return;

    branch(n - 1);
    branch(n - 1);
}

For branch(3), the root invocation creates two branch(2) invocations. Each branch(2) invocation creates two branch(1) invocations, and each branch(1) invocation creates two branch(0) invocations. The completed call tree therefore has twice as many calls on each lower level.

Level n = 3: 1 call   branch(3)
Level n = 2: 2 calls  branch(2), branch(2)
Level n = 1: 4 calls  branch(1), branch(1), branch(1), branch(1)
Level n = 0: 8 calls  branch(0), branch(0), branch(0), branch(0), branch(0), branch(0), branch(0), branch(0)

Time counts all 15 calls in the completed call tree

The total running time includes every invocation, not only the calls that make another recursive call. For branch(3), there is one call at the first level, two at the next, four after that, and eight base-case calls at the bottom. Adding them gives 1 + 2 + 4 + 8 = 15 total calls.

For an input n, the same doubling continues through levels 0 to n. The number of calls on the deepest level is 2^n, so the total number of calls is dominated by that largest level. The constant work done by each invocation, such as checking n == 0, gives a time complexity of O(2^n).

Only four stack frames are active at the deepest point

The completed tree shows every invocation that will happen, but the call stack shows only invocations that have started and have not returned. Follow the first recursive call from branch(3): it starts branch(2), which starts branch(1), which starts branch(0). At that moment, the active path contains four stack frames.

branch(3)
  -> branch(2)
       -> branch(1)
            -> branch(0)

branch(0) returns
branch(1) starts its second branch(0)
that branch(0) returns
branch(1) returns
branch(2) starts its second branch(1)

The first branch(0) returns before the second recursive call inside branch(1) starts. Then branch(1) returns before branch(2) starts its second child. This sequential order means sibling subtrees contribute to total time, but they do not stay active together on the stack.

Time follows the whole tree, but space follows one active path

For branch(3), time counts all 15 invocations in the completed call tree. Auxiliary space counts the largest number of unfinished invocations held by the call stack at one moment, which is the four frames on the path from branch(3) to branch(0). These are different measurements because a returned frame is removed before a sibling invocation begins.

You can analyze similar recursive code with a repeatable test. First count every invocation in the completed call tree to estimate time. Then trace the longest chain of unfinished invocations, stopping when the base case returns, to estimate recursive stack space. Calls made by sibling branches increase the first count, while only the longest active chain controls the second.