In Java the **call stack** keeps track of the methods that you have called since the main method executes. A **stack** is a way of organizing data that adds and removes items only from the top of the stack. An example is a stack of cups. You can grap a cup from the top of the stack or add more cups at the top of the stack.

When you are executing one method (method a) and it calls another method (method b) the method call is placed on the call stack along with information about where it was called from, which tells the run-time where to return to when the current method finishes executing. When method b finishes executing the run-time pops the method b off of the call stack and returns execution to the next line to be executed in method a.

Consider the following class definition.

The code above will cause a run-time error of division by zero when it runs. The `main` method calls the method `test1` (at line 20) which calls the method `test2` (at line 6) which has the divide by zero error (line 14). This can be seen in the call stack shown below which shows the call stack from the top (most recent method) to the bottom (first method call).

When a method calls itself the new method call gets added to the top of the call stack. Execution of the current method pauses while the recursive call is being processed.

Let’s trace the execution of the factorial method defined below.

```
public static int factorial(int n)
{
if (n == 0)
return 1;
else
return n * factorial(n-1);
}
```

What happens when we call `factorial(0)`? It will return 1 (line 4) since n is equal to 0. How about `factorial(1)`? It will return `1 * factorial(0)`. We already know that `factorial(0)` returns 1, but the computer won’t *remember* that. It will execute `factorial(0)` and return the result (1). So `factorial(1)` returns `1 * 1 which is 1`.

How can you show what is happening in a recursive call? Here is one way to do it. The lines below show the call stack (from the bottom of the stack, or the beginning, to the top of the stack, or the most recent call) for a call to `factorial(5)`.

```
factorial(5) returns 5 * factorial(4)
factorial(4) returns 4 * factorial(3)
factorial(3) returns 3 * factorial(2)
factorial(2) returns 2 * factorial(1)
factorial(1) returns 1 * factorial(0)
factorial(0) returns 1
```

Once factorial(0) executes and returns 1 that value can be substituted back into the previous method call, starting at the top of the stack and working our way back to the bottom of the stack (beginning).

```
factorial(5) returns 5 * factorial(4) = 5 * 24 = 120
factorial(4) returns 4 * factorial(3) = 4 * 6 = 24
factorial(3) returns 3 * factorial(2) = 2 so 3 * 2 = 6
factorial(2) returns 2 * factorial(1) = 1 so 2 * 1 = 2
factorial(1) returns 1 * factorial(0) = 1 so 1 * 1 = 1
factorial(0) returns 1
```

So `factorial(5)` returns 120.

A great way to see the call stack in action is to use Jeloit (see http://cs.joensuu.fi/jeliot/ for the software and http://ice-web.cc.gatech.edu/dl/?q=node/729 for a step by step tutorial about how to use Jeliot).

**Check your understanding**

11-3-1: Given the method defined below what does the following return: factorial(6)?

public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n-1); }

11-3-2: Given the method defined below what does the following return: mystery(5)?

public static int mystery(int n) { if (n == 0) return 1; else return 2 * mystery (n - 1); }

11-3-3: Given the method defined below what does the following print: mystery(4,3)?

public static int mystery(int n, int a) { if (n == 1) return a; return a * mystery(n-1,a); }

Let’s trace the execution of the bunny ears method defined below.

```
public static int bunnyEars(int bunnies)
{
if (bunnies == 0) return 0;
else if (bunnies == 1) return 2;
else return 2 + bunnyEars(bunnies - 1);
}
```

What happens when we call `bunnyEars(0)`? It will return 0 since n is equal to 0 (line 3). How about `bunnyEars(1)`? It will return 2 since n is equal to 1 (line 4). What about `bunnyEars(5)`?

```
bunnyEars(5) returns 2 + bunnyEars(4)
bunnyEars(4) returns 2 + bunnyEars(3)
bunnyEars(3) returns 2 + bunnyEars(2)
bunnyEars(2) returns 2 + bunnyEars(1)
bunnyEars(1) returns 2
```

This approach shows the call stack from bottom to top. Once bunnyEars(1) executes and returns 2 that value can be substituted back into the previous method call, starting at the top and working our way back toward the bottom (or beginning) of the call stack.

```
bunnyEars(5) returns 2 + bunnyEars(4) = 2 + 8 = 10
bunnyEars(4) returns 2 + bunnyEars(3) = 2 + 6 = 8
bunnyEars(3) returns 2 + bunnyEars(2) = 2 + 4 = 6
bunnyEars(2) returns 2 + bunnyEars(1) = 2 + 2 = 4
bunnyEars(1) returns 2
```

So `bunnyEars(5)` returns 10.

**Check your understanding**

11-3-4: Given the method defined below what does the following print: mystery(1234)?

public static void mystery (int x) { System.out.print(x % 10); if ((x / 10) != 0) { mystery(x / 10); } System.out.print(x % 10); }

11-3-5: Given the method defined below what does the following return: mystery(“xyzxyxy”)?

public static int mystery(String str) { if (str.length() == 1) return 0; else { if (str.substring(0,1).equals("y")) return 1 + mystery(str.substring(1)); else return mystery(str.substring(1)); } }

11-3-6: Given the method defined below what does the following return: mystery(“xyzxyxy”)?

public static int mystery(String str) { if (str.length() == 1) return 0; else { if (str.substring(0,1).equals("y")) return 1 + mystery(str.substring(1)); else return mystery(str.substring(1)); } }