Understanding Recursion with the Factorial Example

Programming languages usually have their own internal Stack. In case of Java it’s the Java Stack. When any new thread is launched, the JVM creates a new Java stack for the particular thread. It stores the thread’s state in discrete frames. The JVM performs PUSH and POP operations on the Java stack.

When a thread invokes a method, JVM creates a new frame and pushes it on to the Java stack. The newly pushed frame becomes the current frame. As the method executes, it uses the frame to store parameters, local variables, intermediate computations, and other data.

Recursion is the process in which a function calls itself. The function is called as recursive function. A recursive function performs a bigger task part by part by calling itself to perform the subtasks. Every recursive function has a base case, it’s the point when the function is able to return some value without calling itself. Below is the format of a recursive function.

if(Base case) {

            return Base Case Value;

} else {

            return (Compute some work followed by recursive a call)

}

Code to find the factorial of an integer:

public static int factorial(int n) {

            if(n==0 || n==1){

                        return 1;

            }

            return n * factorial(n-1);

}

Let’s try to visualise the flow of execution of the above piece of code. Factorial of 5 is 120.

Factorial of 5 = 5 * 4 * 3 * 2 * 1 = 120

When the factorial method is called with 5, JVM creates a frame and pushes it onto the Java stack.

Now the code returns '5 * factorial(4)'. Since, once again there’s a method call (same factorial method), JVM creates a new frame and pushes it on the Java stack.

Similarly, the method keeps calling itself till it reaches the base case.

Once base case is reached it returns without making any recursive call. In our case when factorial is called with 1, it simply returns 1. JVM pops the current frame, the result of the subtask(1) is required by the next frame for computation.

Now, the top most frame is again popped. The result is computed to be 2. This result is used to compute the next frame.

Now the current stack frame computes the result (3*2 = 6), and JVM pops the frame from the Java stack.

Now, the current frame computes the subtask result (4 * 6 = 24). JVM pops the frame from the Java stack.

Now, there’s only one frame on the Java stack. It computes the final result (5 * 24 = 120). 

JVM pops the frame, and the recursive function completes.

We will try out some more recursive functions. Hope you've enjoyed the post :)