0

I am getting closer to debunking this recursive mystery, there is only one thing left that I can not trace in this line of the code, and that is the final return value wich is 243 if i call rec() passing it the value 5. this should be the trace:

n: 4 *3: 12
n: 3 *3: 9
n: 2 *3: 6
n: 1 *3: 3
n: 0 *3: 0
n: 1 *3: 3

result: 243

Correct? how does it get the result of 243?

int rec(int n)
{
if (n == 0)
    return 1;


return 3 * rec(n-1);
}
2
  • This effectively calculates 3^x.
    – user529758
    Dec 4, 2012 at 11:56
  • @JanDvorak overseen that. Fixed.
    – user529758
    Dec 4, 2012 at 11:59

3 Answers 3

8

Your function computes : 3^n.

The number 3 is multiplied with the result of the n-1 calls.

f(n) = 3 * f(n-1);

f(0) = 1;

f(1) = 3 * f(0) = 3 * 1 = 3;

f(2) = 3 * f(1) = 3 * 3 = 9;

f(3) = 3 * f(2) = 3 * 3 * f(1) = 3 * 3 * 3 = 27

. . .

f(5) = 3 * 3 * 3 *3 * 3 = 243

2
  • f(1) should be 3*f(0) = 3*1, not 3.
    – bitmask
    Dec 4, 2012 at 12:03
  • @melpomene if someone does not understand that f(0)=1 I think recursion is the least of his problems :).
    – giorashc
    Dec 4, 2012 at 12:57
2

This function computes

3^n where n >= 0

If you pass 5 it computes 3 * 3 * 3 * 3 * 3 * (1) = 243

-1

It does only multipling on 3, four times:

return 3 * rec(n-1);

I think you wanted something like this:

return n * rec(n-1);
5
  • 4
    What makes you think this is the desire? Dec 4, 2012 at 11:58
  • I have put 3 there just so I can study how the recursive algorithm works and calculates it´s result Dec 4, 2012 at 11:59
  • So you're saying that instead of return n * rec(n-1); he wants return n * rec(n-1);? I think that's not what you want to say.
    – mah
    Dec 4, 2012 at 12:01
  • I'm updating several times before final variant, sorry Dec 4, 2012 at 12:05
  • Now that your recommendation is correctly different than the original code, see @JanDvorak's comment... what makes you think the OP desires a factoral function?
    – mah
    Dec 4, 2012 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.