Recursion and Memory Visualization

This lesson will discuss how recursive methods use the stack.

We'll cover the following

Memory allocation to methods

When a method is called, the state of the method is placed on the call stack along with the information about where it was called from. This tells the run-time where it should return to when the current method finishes executing. Each recursive call pushes a new stack frame. A stack frame consists of information such as the return address, argument variables, and local variables related to that method call.

When a method calls itself, the new method call gets added to the top of the call stack and execution of the current method pauses while the recursive call is being processed. When the base case is reached the stack frames start popping from the stack until the stack becomes empty.

Example

Computing Factorials

What is a Factorial?

A factorial is the product of an integer and all the positive integers below it. It is denoted by the symbol: !!

For example, 4! (read as four factorial) is denoted as follows:

4!=4×3×2×1=244!=4\times3\times2\times1=24

6!=6×5×4×3×2×1=7206!=6\times5\times4\times3\times2\times1=720

Code

Press + to interact
class Factorial {
    // Recursive function
    private static int factorial(int n) {
      // Base case
      if (n == 1) {
        return 1;
      }
      // Recursive case
      else {
        return (n * factorial(n-1));
      }
    }
    public static void main( String args[] ) {
        // Calling from main
        int result = factorial(5);
        System.out.println("Factorial of 5 is: " + result);
    }
}

We will now briefly discuss the two main parts of a recursive method, the base case and the recursive case, implemented in the code above.

The Base Case

We have defined the base case on line 5 where it states that when the variable n equals 11, the method should terminate and start popping frames from the stack.

The Recursive Case

This is similar to the formula given above for the factorial. For example, in case of 33 factorial, 3!=3×2×1=63!=3\times2\times1=6 we multiply the original number n with the integer that precedes it, n-1, and the recursive call, factorial(n-1), is made until n reaches 11.

Visualizing through Stack

The following illustration may help you to understand the code through a stack:

Interesting concept, right? Let’s discuss the two types of recursion concepts in the next lesson.