How does Recursion Work: An Example

For purposes of this demonstration, we use the following recursive Java method: 

/* Given a natural number n, returns n! 
** ("n factorial"), the product of the 
** integers in the range [1..n].
*/
public static int factorial(int n) {
   if (n == 0) { return 1; }
   else {
      int temp = factorial(n-1);
      return n * temp;
   }
}

Now imagine that a client program calls this method and passes 3 to it. The following figure shows snapshots of the run-time stack (or call stack) as the recursive calls descend to the base case. X refers to the address, within the client program's calling method, of the instruction at which execution should continue after the factorial() method has returned its result. Z refers to the address, within the factorial() method itself, of the instruction that assigns the value returned by the recursive call to the local variable temp. Meanwhile, '-' means undefined. 

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












+----------+
| temp : - |
| n    : 3 |
| RA   : X |
+----------+
| frame of |
|  caller  |
+----------+
|  other   |
|  frames  |
+----------+
 








+----------+
| temp : - |
| n    : 2 |
| RA   : Z |
+----------+
| temp : - |
| n    : 3 |
| RA   : X |
+----------+
| frame of |
|  caller  |
+----------+
|  other   |
|  frames  |
+----------+
 




+----------+
| temp : - |
| n    : 1 |
| RA   : Z |
+----------+
| temp : - |
| n    : 2 |
| RA   : Z |
+----------+
| temp : - |
| n    : 3 |
| RA   : X |
+----------+
| frame of |
|  caller  |
+----------+
|  other   |
|  frames  |
+----------+
+----------+
| temp : - |
| n    : 0 |
| RA   : Z |
+----------+
| temp : - |
| n    : 1 |
| RA   : Z |
+----------+
| temp : - |
| n    : 2 |
| RA   : Z |
+----------+
| temp : - |
| n    : 3 |
| RA   : X |
+----------+
| frame of |
|  caller  |
+----------+
|  other   |
|  frames  |
+----------+

Now we show snapshots of the call stack as recursion "unwinds": 

public static int factorial(int n) {
   if (n == 0) { return 1; }
   else {
      int temp = factorial(n-1);
      return n * temp;
   }
}
 
+----------+
| temp : - |
| n    : 0 |
| RA   : Z |
+----------+
| temp : - |
| n    : 1 |
| RA   : Z |
+----------+
| temp : - |
| n    : 2 |
| RA   : Z |
+----------+
| temp : - |
| n    : 3 |
| RA   : X |
+----------+
| frame of |
|  caller  |
+----------+
|  other   |
|  frames  |
+----------+
 




+----------+
| temp : 1 |
| n    : 1 |
| RA   : Z |
+----------+
| temp : - |
| n    : 2 |
| RA   : Z |
+----------+
| temp : - |
| n    : 3 |
| RA   : X |
+----------+
| frame of |
|  caller  |
+----------+
|  other   |
|  frames  |
+----------+
 








+----------+
| temp : 1 |
| n    : 2 |
| RA   : Z |
+----------+
| temp : - |
| n    : 3 |
| RA   : X |
+----------+
| frame of |
|  caller  |
+----------+
|  other   |
|  frames  |
+----------+
 












+----------+
| temp : 2 |
| n    : 3 |
| RA   : X |
+----------+
| frame of |
|  caller  |
+----------+
|  other   |
|  frames  |
+----------+