Recursion Basics

Question

I have read about recursion and I'm very much interested in understanding a very basic thing which I'm using in the factorial. Since I have researched about it well, saw particular videos of it, but somehow this thing is very much confusing me. I have the option of writing the mug up a code and move ahead, but I'm into learning things well.

From here are the sources for the recursion :

• Recursion in Java
• Recursion 3

I have one thing to ask since in the code I have seen one thing that is the if-else. I know about if else condition very well. But in here things are a little bit complicated.

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

In the above code, here the result appears to be correct but somehow what I think is why it is not returning only 1 when it satisfies the condition, and how come it is printing the correct result. There is a single catch which I'm not been able to grasp. Please help me to get through this.

Consider me as a learner in the coding field. Thanks

Answer 1

Simple dry run would lead you to your answer. N is being subtracted by one everytime till it hits 1.

For example lets consider N as 4

It would go into the else statement, that would become return 4 * fact(4-1)

The recursion now has 4 * fact(3)

fact 3 would lead to 3 * fact (2)

Which would equate the first equation to be equal to 4 * 3 * fact(2);

It happens until N becomes 1 so the whole equation would be like 4 * 3 * 2 * 1

at 1 the recursion stops and we start returning through the recursion stack.

Hope it clarifies your question.

Answer 2

Viewing a recursive function as a tree makes it much easier to understand for the beginners. Every recursive function operates in two steps:

Step 1: Tree expansion

Step 2: Back substitution

Consider the image below. In the image, the color red shows step 1 and color green shows step 2. You can not do step 2 until step 1 terminates. This is the reason, you need to have a termination condition in every recursive function otherwise; the tree will keep on expanding your program will run out of memory.

When you invoked fact(4), it expanded as 4 * fact(3) which further expanded as shown below:

fact(4) = 4 * fact(3)
fact(3) = 3 * fact(2)
fact(2) = 2 * fact(1)
fact(1) = 1

Now, all you need to do is back-substitute the values in order to obtain the value of fact(4).

On hardware, the recursive function expands just like the tree shown above. This happens on the stack and each node of the tree is an activation record. See this answer to know more about activation record.