How recursion works

C:\
  myfile.txt
  picture.jpg
  Programs
    notepad.exe
    browser.exe
    Utility
      chars.exe
  logfile.txt
  ...

In this example, the names with capital letters are directories, with indentation representing the level in the directory tree. So notepad.exe, browser.exe and Utility are inside Programs, and chars.exe is in turn inside Utility; logfile.txt, with the same indentation as myfile.txt etc, is in the root of C:.

Now let's consider what happens when our recursive routine scans down this directory structure. We initially call our listFilesInDirectory() method, passing in the root directory C:\. Then our method calls listFiles() and gets the list of files and directories in the root of C:. The method starts looping over this list, printing out the names of File objects that aren't directories. All is simple, therefore, until we get to the directory Programs. At this point, we want to make a recursive call to listFilesInDirectory(). Eventually, that call will return, and when it returns, we need to remember "where we got to" in the list of files in C:, and continue listing from logfile.txt.

The stack

To remember "where it got up to", the program has a stack. A stack is a special area of memory set aside for remembering "where to go back to" every time the program makes a method call. (Strictly speaking, every thread has its own stack, because different threads run and make method calls independently of one another.) Conceptually, you can imagine it like a pile of little note papers. When it needs to call a method, the program writes a little "note" to itself, noting the values of all the variables inside the method at the point it got up to, plus where in the method it needs to come back to. It then places that note on top of the "pile" (the stack)¹ and calls the method.

The call to list the contents of Programs will eventually get down to the subdirectory Utility and have to make another recursive call. So again, a "note" is placed on the stack. Once the call has gone through the contents of Utility, the top note is pulled off the stack, telling the Java runtime whereabouts in the processing of the Programs directory to go back to. Then, when that directory has been completed, the top note is again pulled off the stack. At this point, the top note is the one originally placed there before making the call to list the contents of Programs— in other words, we end up at the point we left off while going through the C: directory. So to complete that loop, the file logfile.txt is processed, and the method exits, completing the overall process.

Local variables on the stack

So what actually goes on the stack? What do the "little notes" that the Java Virtual Machine writes to itself actually look like? Well, we said that the stack is an area of memory. When our program (or, more precisely, our thread) starts, a fixed-size block of memory is reserved for its stack. The computer keeps a stack pointer, which points to the top of the stack at any one time. So to put something on top of the stack, we write it to the memory location indicated by the stack pointer at the current moment in time, then "nudge" the stack pointer forward by the size of the item we've just added to the stack. To take an item back off the top of the stack, we nudge the stack pointer backwards by the size of the item we want to take off, then read the data from that memory location.

Now, when we call a method, an item is placed on the stack for each local variable inside that method. Local variables are variables that we either pass into the method (in our case, the directory/subdirectory to be listed), or variables that we declare inside the method (for example, we declared a variable called files, which is the array of files inside the directory being listed, f, which is the current file we're looking at, and implicitly, we also had an Iterator object to iterate over the array). Figure 2 illustrates the idea. In this case, a method (represented in blue) was initially called, which overall had two local variables. It in turn called another method, represented in green. Then it called a further method, represented in yellow, which had three variables. A possible piece of code to produce this layout might be roughly as shown in Figure 3:

void blue(int x) {
  int y = 17 * x;
  green(y);
}

void green(int z) {
  for (int i = 0; i < z; i++) {
    int val = z * i;
    yellow(val);
  }
}

void yellow(int x) {
  int a = x * 7;
  Object o = new Object();
  ...
}

As you reconcile the stack usage shown in Figure 2 with the code in Figure 3, notice that, for example, in the blue() method, both the method parameter (x) and the variable y declared inside the method take up space on the stack. Notice that if a variable is an object, only the reference is placed on the stack. The actual object data is allocated on the Java heap, a different area of memory.

In general, each method has its own well-defined "area" on the stack, and while a particular method is running, Java knows whereabouts on the stack all the variables for the current method start. The Java bytecode that is running actually refers to local variables by number, so accessing, say, variable x actually means "access the data from position 0 of the section of stack memory for the current method". (When the JIT compiler translates the bytecode into native machine code, it effectively compiles it into code that says "access the data at stack pointer plus offset x", knowing for a given variable what the appropriate value of x is.) Because the stack is actually an area of memory rather than a pile of notes, variables can often be accessed directly from the stack.

A subtlety that we haven't included in Figure 2 is that when we call a method, we also store the current program counter: i.e. whereabouts in the code we actually are. That way, when the called method returns, it knows where to jump back to!

In other words:

• calling a method often means putting the parameter values on to the stack, putting the current program counter on the stack, moving the stack pointer on by an appropriate amount, then jumping to that method's code;
• returning from a method is essentially the reverse process: the old program counter is pulled back of the stack, the stack pointer is moved back to point to the previous method's variables, then we "jump back" and continue executing code from the location after old program counter.

Implications for recursion

So what implications does this all have for recursion? Well, each time we make a recursive call, we "eat up" a bit more space on the stack. So the maximum depth of recursion is limited by:

• our thread's stack size (the amount of memory allocated to the stack);
• the number of parameters and local variables used on each call to our method.