Thread: Factorial Help

What is output by the following?

Code:

printf("%d\n", r(5,3));
...
int r (int a, int b) {
    if (a > b) return a * r(a-1, b);
    else if (b > 1) return b * r(1, b-1);
    else return 1;
}

===========

The answer is 120, but i don't get it. Obviously the first condition is true, so the C compiler will execute return a * r(a-1, b); which is 5*(4,3). However, im not sure why the compiler is executing 5*4*3*2*1, i thought it would just return5*4*3 and stop. Can someone explain this to be step by step ? Thanks.

The best way (until you can do this in your head) is to write it down. Even those of us who have been doing this for 20+ years still have to write it down sometimes.

The trick is to make sure you get the call correct each time, and WRITE IT DOWN.

If you don't write it down you'll miss something.

Originally Posted by Kennedy

The best way (until you can do this in your head) is to write it down. Even those of us who have been doing this for 20+ years still have to write it down sometimes.

The trick is to make sure you get the call correct each time, and WRITE IT DOWN.

If you don't write it down you'll miss something.

I did write it down, i have shown what i wrote down in the first post, but my logic is not correct somewhere so was hoping that someone can denote my flaws and steer me in the appropriate direction.

Originally Posted by purplehaze

What is output by the following?

Code:

printf("%d\n", r(5,3));
...
int r (int a, int b) {
    if (a > b) return a * r(a-1, b);
    else if (b > 1) return b * r(1, b-1);
    else return 1;
}

===========

The answer is 120, but i don't get it. Obviously the first condition is true, so the C compiler will execute return a * r(a-1, b); which is 5*(4,3). However, im not sure why the compiler is executing 5*4*3*2*1, i thought it would just return5*4*3 and stop. Can someone explain this to be step by step ? Thanks.

It's not 5*(4,3), it's 5*r(4,3). So now you have to figure out what r(4,3) is (big hint: not 4*3).

The first two times it's called the first if loop is triggered. The next 2 times it's called, the second loop is triggered and the same thing is being done to b that was done to a. The final time it's called it will return the final else statement.

so the calls will run like this, if my logic is not mistaken

PS: Make sure you've written it out EXTENSIVELY; don't just write down values step by step, write down each STEP step by step WITH the values in place;if you still cant figure it out, here's what it looks like. But again, make sure that you've tried it step by step through the code.

Did you try to understand what the if and else statements try to do?




















------------------

Code:

r(5,3)
   5>3 so return 5*r(4,3)
      4>3 so return 4*r(3,3)
         3 does not > 3 so go to second statement
         3>1 so return 3*r(1,2)
            1 does not > 2 so go to second statement
            2>1 so return 2*r(1,1)
               1 does not >1 so go to second statement
               1 does not > 1 so go to third statement
               return 1
            2*1
        3*2*1
    4*3*2*1
5*4*3*2*1

Tada.

Originally Posted by Soulzityr

The first two times it's called the first if loop is triggered. The next 2 times it's called, the second loop is triggered and the same thing is being done to b that was done to a. The final time it's called it will return the final else statement.

so the calls will run like this, if my logic is not mistaken

PS: Make sure you've written it out EXTENSIVELY; don't just write down values step by step, write down each STEP step by step WITH the values in place;if you still cant figure it out, here's what it looks like. But again, make sure that you've tried it step by step through the code.

Did you try to understand what the if and else statements try to do?




















------------------

Code:

r(5,3)
   5>3 so return 5*r(4,3)
      4>3 so return 4*r(3,3)
         3 does not > 3 so go to second statement
         3>1 so return 3*r(1,2)
            1 does not > 2 so go to second statement
            2>1 so return 2*r(1,1)
               1 does not >1 so go to second statement
               1 does not > 1 so go to third statement
               return 1
            2*1
        3*2*1
    4*3*2*1
5*4*3*2*1

Tada.

I wish this form had a thank-you option, thanks!!!

Make sure you try to follow it on your own without the guided instructions so you can figure out similar problems later.