Space Complexity of Recursion

A recursive method can use memory even when its code does not allocate anything. It might never write new int[...], copy an array, or keep a running count. By the rule from the last section, you would say its auxiliary space is $O(1)$. That is often wrong, because the method is using memory on the call stack.

Every time a method is called, Java creates a function activation record for that call, also called a stack frame. It is a block of memory holding that call’s parameters, its local variables, and the bookkeeping needed to return. The frame stays on the stack until the call returns. So if a method calls itself before it finishes its own work, the caller’s frame is still there when the callee’s frame goes on top, and the number of frames on the stack grows.

To find a recursive method’s auxiliary space, we ask for the maximum depth the call stack reaches.

Here are two implementations of countUp, which prints the numbers from 1 to n. The first is iterative and the second is recursive:

public static void countUpItr(int n) {
  for (int i = 1; i <= n; i++) {
    System.out.println(i);
  }
}

public static void countUpRec(int n) {
  if (n > 1) {
    countUpRec(n - 1);
  }
  System.out.println(n);
}

The iterative countUpItr keeps only the loop counter i, so it is $O(1)$ auxiliary space.

Now trace the recursive one. countUpRec(n) calls countUpRec(n - 1) before it prints anything, so its frame is still on the stack. That call does the same thing, and so does the next, all the way down to countUpRec(1). Nothing has printed yet at that point, and nothing has returned, so all $n$ frames are on the stack at once. One frame per number gives a stack of depth $n$, so the recursive version uses $O(n)$ auxiliary space.

Both versions print $n$ numbers and do a constant amount of work per number, so both run in $O(n)$ time.

The auxiliary space of a recursive method is the maximum depth the call stack ever reaches, times the size of one frame. A frame is a constant size here, so we report the depth.