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.

Answer 3

The recursive function is a function which calls by itself

It allows programmers to write efficient programs using a minimal amount of code.

The downside is that they can cause infinite loops and other unexpected results if not written properly.

In order to write a recursive function.

1. The first point to consider is when should you decide on coming out of the loop which is the if loop

2. The second is what process to do if we are our own function

From the given example:

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

From the above example

if(n <=1)
     return 1;

Is the deciding factor when to exit the loop

else 
     return n * fact(n-1);

Is the actual processing to be done

Let me the break the task one by one for easy understanding.

Let us see what happens internally if I run fact(4)

1. Substituting n=4

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

If loop fails so it goes to else loop so it returns 4 * fact(3)

2. In stack memory, we have 4 * fact(3)

   Substituting n=3

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

If loop fails so it goes to else loop

so it returns 3 * fact(2)

Remember we called ```4 * fact(3)``

The output for fact(3) = 3 * fact(2)

So far the stack has 4 * fact(3) = 4 * 3 * fact(2)

3. In stack memory, we have 4 * 3 * fact(2)

   Substituting n=2

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

If loop fails so it goes to else loop

so it returns 2 * fact(1)

Remember we called 4 * 3 * fact(2)

The output for fact(2) = 2 * fact(1)

So far the stack has 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

3. In stack memory, we have 4 * 3 * 2 * fact(1)

   Substituting n=1

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

If loop is true

so it returns 1

Remember we called 4 * 3 * 2 * fact(1)

The output for fact(1) = 1

So far the stack has 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

The result of fact(4) = 4 * 3 * 2 * 1 = 24

Answer 4

Hi there fellow code learner, i hope people on StackOverflow will have mercy with your question, because they never had any with my questions.

Anyways, lets run through your code and see what exactly is happening:

im gonna call "fact(5)" in my main. The following is a representation of what is going on in the background:

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

and fact 4 will be:

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

and so on:

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

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

public static int fact(1){
  if(1 <= 1) //true for the first time
     return 1;
  else 
     return 1 * fact(0);
}

in "fact(1)" the if case triggers for the first time, and it returns 1. If we now work our way back upwards:

//fact(1) = 1
public static int fact(2){ //returns the else case, 2*1 = 2 so fact(2) = 2
  if(2 <= 1)
     return 1;
  else 
     return 2 * 1;
}

public static int fact(3){ //same here, fact(2) = 2, so we end up with 3*2 = 6
  if(3 <= 1)
     return 1;
  else 
     return 3 * 2;
}

public static int fact(4){
  if(4 <= 1)
     return 1;
  else 
     return 4 * 6; //fact(3) = 6, so we return 4*6 = 24
}

public static int fact(5){
  if(5 <= 1)
     return 1;
  else 
     return 5 * 24; //fact(4) = 24, so we return 5*24 = 120
}

i hope this helps clearing up your question.

Answer 5

I think the best way to understand this is by an example. For instance, if you call fact(3), the code exeuction would be like this (as a pseudocode):

fact(3)

3 is greater than 1 so
return 3 * fact(2)  ---> Lets wait for this

fact(2)

2 is greater than 1 so
return 2 * fact(1)  ---> Lets wait for this

fact(1)

1 is same as 1 so
return 1 ---> 1 will be the result of fact(1)

Now lets back to fact(2)

return 2 * 1 --> 2 this will be the result of fact(2)

Now lets back to fact(3)

return 3 * 2 ---> This give 6, and it is the final result of fact(3)

Answer 6

Recursion is used when you can divide your task into similar small tasks. And leverage this to complete a large task. Like this case factorial of number can be represented as the number multiplied to the factorial of (number-1) until it becomes 1. where factorial of 1 and 0 is 1.

So <=1 is one exception condition that needed to be handled separately and then break further calculation.

That's the reason if clause handle <=1 condition and else clause call the same fact method to calculate factorial of n-1. Look at the comments in the code below.

public static int fact(int n) {
    if (n <= 1) {
        // if a number is 1 or less than on then factorial will be 1
        return 1;
    } 
    else {
        /*this part will execute only of number is greater than 1, ex 2,3
         * According to factorial logic, factorial of a number n will be (n * factorial of (n-1))
         * Ex: factorial of 2 = 2*1
         *  factorial of 3 = 3*2*1
         *  factorial of 4 = 4*3*2*1
        */
        return n * fact(n - 1);
    }
}

Answer 7

Alok, Let's say, you pass 3 and now the first iteration is waiting for the outcome from the function call. Now this call triggers another call and it waits for the reault. Finally, when it's 1, returns 1 and that call has the answer and thus it multiies and sends the reault back. Thus return finally reaches the first call which is waiting and the final answer is returned. In easiest way you called a person(a) and that person called another person(b) and that person called another one (c)who gave him a reply. Now as c gave reply, b processes that reply and gives it to a who in turn process that reply and gives it back to you. This is the reason why you got correct answer instead of 1 in the recursive program. Hope you understood that.

Thanks Vino V