What is the logic of the recursion

Question

Here is I have a factorial code using recursion.

class Factorial
{
    public static void main(String args[])
    {
       Factorial f = new Factorial();
       System.out.println(f.fact(Integer.parseInt(args[0])));
    }

    private int fact(int num)
    {
        int result;
        if(num == 1)
             return 1;

        result = fact(num - 1) * num;
        return result;
    }
}

Now to run this program, I did this

D:\>java Factorial 3

Now according to the logic when it enters the fact function, where num = 3, so it will skip to

result = fact(num - 1) * num;

Here it will become

result = fact(3 - 1) * num;

i.e. result = fact(2) * num;

In this step, I am little confused Does it execute whole step i.e.

result = fact(num - 1) * num;

or just the fact(num - 1)

According to the logic, what it should do is call the fact function. So, the control of the program again reaches to the start of the fact function where num = 2. It will again skip to

result = fact(num - 1) * num;

So, it will become

result = fact(2 - 1) * num;

i.e. result = fact(1) * num;

Now again, it should call the fact function without executing the whole syntax & again reaches to the start of the fact method where num = 1. This time num == 1 will be matched & 1 will be returned. Now it will return to

result = fact(num - 1) * num;

So, it will become

result = fact(1 - 1) * num;

i.e. result = fact(0) * num;

Now what will happen next ?

Am I going right ? If not what will be the correction ?

I dont clearly understand the flow of this recursion program.

Have you tried executing this in a debugger, and watching the call stack? It's not really clear what you're asking, to be honest. — Jon Skeet
– Jon Skeet, Commented Aug 6, 2015 at 6:19
for num = 2 [..] So, it will become result = fact(1 - 1) * num; why would you think that? — Mateusz Dymczyk
– Mateusz Dymczyk, Commented Aug 6, 2015 at 6:21
in every steps it executes fact(num - 1) and move forwards by calling the same method again but at the last step control moves backward in order to complete the method body — singhakash
– singhakash, Commented Aug 6, 2015 at 6:23
there's nowhere it only calculates fact(num - 1) but not multiply by num — phuclv
– phuclv, Commented Aug 6, 2015 at 6:28
Any decent debugger will do that. Download Eclipse for free and step through the code that way... — Jon Skeet
– Jon Skeet, Commented Aug 6, 2015 at 7:09

Siguza · Accepted Answer · 2015-08-06 06:26:33Z

2

So, it will become
result = fact(1 - 1) * num;

Nope. For num = 2,

result = fact(num - 1) * num;

becomes

result = 1 * num; // i.e. 1 * 2

fact returns a value, which means the entire call has to be replace with that value.
Not sure why you would even think num changes at all. You have no num = ... in your code.

edited Aug 6, 2015 at 6:26

answered Aug 6, 2015 at 6:20

Siguza

24.7k6 gold badges58 silver badges105 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Dakshinamurthy Karra · Accepted Answer · 2015-08-06 06:27:35Z

2

I added some trace into the program. Execute it and see the output. Should be easy to follow.

package snippet;

class Factorial {
    public static void main(String args[]) {
        Factorial f = new Factorial();
        System.out.println(f.fact(Integer.parseInt("5")));
    }

    private int fact(int num) {
        int result;
        if (num == 1)
            return 1;

        result = fact(num - 1) * num;
        System.out.println("fact(" + num + ") = " + result + " = fact(" + (num - 1) + ") * " + num);
        return result;
    }
}

fact(2) = 2 = fact(1) * 2
fact(3) = 6 = fact(2) * 3
fact(4) = 24 = fact(3) * 4
fact(5) = 120 = fact(4) * 5
120

answered Aug 6, 2015 at 6:27

Dakshinamurthy Karra

5,4931 gold badge19 silver badges31 bronze badges

Comments

Madlefu · Accepted Answer · 2015-08-06 07:32:05Z

Your logic is right but you have made 3 basic errors. if we take your example; First you run the program

D:\>java Factorial 3

then you have your first mistake because according to the logic all "num" have to be replaced by "3". So you get:

result = fact(3 - 1) * 3;

ie:

result = fact(2)*3;

then we have the second mistake because according to the definition of fact(num),

fact(2) = fact(2-1)*2

so we actually have

result = (fact(2-1)*2)*3

which is evaluated in

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

and here stand the third mistake because again according to fact(num) definition : fact(1) = 1 and not fact(1) = fact(1-1)*1 so we finally have:

result = ((1)*2)*3

To be more explicit if you follow all call sequence in the debugger you 'll have something like this( I put between brackets the value of the variable):

   private int fact(num{3})
    {
        int result;
        if(num{3}== 1)
             return 1;

        result = fact(num{3} - 1) * num{3};

            private int fact(num{3-1})
            {
                int result;
                if(num{3-1}== 1)

                result = fact(num{3-1} - 1) * num{3-1};

                    private int fact(num{3-1-1})
                    {
                        int result;
                        if(num{3-1-1}== 1)
                             return 1;
                    }

                return result{1*{3-1}};
            }
        return result{{1*{3-1}}*3};
    }

Jason · Accepted Answer · 2015-08-06 06:26:25Z

1

Unless we hit the stop condition:

fact(num) = fact(num - 1) * num;

Therefore:

fact(3) = fact(3 - 1) * 3;

Keeping in mind that fact(1) = 1 (from the if statement early in the fact() method):

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

Replacing each element:

fact(3) = 1 * 2 * 3;

The recursion is used to repeatedly dive deeper into the process until a stop condition is encountered - in this case when num = 1.

answered Aug 6, 2015 at 6:26

Jason

11.8k3 gold badges45 silver badges48 bronze badges

Comments

Hei · Accepted Answer · 2015-08-06 06:23:37Z

1

The call f.fact(3) is expanding through the following steps:

1. result = fact(3 - 1) * 3 = fact(2) * 3
2. result = (fact(2 - 1) * 2) * 3 = (fact(1) * 2) * 3
3. result = 1 * 2 * 3 because fact(1) returns 1.

answered Aug 6, 2015 at 6:23

Hei

1,9544 gold badges26 silver badges38 bronze badges

Comments

Rohit sharma · Accepted Answer · 2015-08-06 06:45:02Z

1

Your implementation is correct, But it will never reach fact(1-1) * 1 state ,as you return from method at if(num == 1).

num variable is limited to scope of method parameter. So for every call to fact method num variable is assigned a new value (i.e. num-1) and which is limited to that parameter scope only. So when fact(num-1) returns , value of num will be the original value and not the num-1.

answered Aug 6, 2015 at 6:45

Rohit sharma

714 bronze badges

Comments

programmer · Accepted Answer · 2015-08-06 07:06:38Z

1

The flow of your example is like this

step 1. fact(3)*3;  //calling the function with num value 3
step 2. fact(2)*2;  //calling fact() method again with num=2
step 3. fact(1)*1;  //now num == 1 will be matched & 1 will be returned.

    i. e., 1 * 1 = 1; //now, steps 2 and 1 will be performed respectively

step 2. 1 * 2 = 2;
step 1. 2 * 3 = 6;

So, the final answer will be 6

Note: In step 3, the value is returned, so it will not again call this
result = fact(0) * num; //which you have mentioned in question.

answered Aug 6, 2015 at 7:06

programmer

4924 silver badges5 bronze badges

Collectives™ on Stack Overflow

What is the logic of the recursion

7 Answers 7

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related