Tracing simple recursive function

Question

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);
}

This effectively calculates 3^x.

user529758
– user529758

2012-12-04 11:56:43 +00:00
Commented Dec 4, 2012 at 11:56 — user529758
– user529758, Commented Dec 4, 2012 at 11:56
@JanDvorak overseen that. Fixed.

user529758
– user529758

2012-12-04 11:59:17 +00:00
Commented Dec 4, 2012 at 11:59 — user529758
– user529758, Commented Dec 4, 2012 at 11:59

melpomene · Accepted Answer · 2012-12-04 12:06:01Z

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

edited Dec 4, 2012 at 12:06

melpomene

86.2k8 gold badges96 silver badges155 bronze badges

answered Dec 4, 2012 at 11:56

giorashc

13.7k3 gold badges38 silver badges76 bronze badges

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

2 Comments

bitmask Over a year ago

f(1) should be 3*f(0) = 3*1, not 3.

giorashc Over a year ago

@melpomene if someone does not understand that f(0)=1 I think recursion is the least of his problems :).

tafa · Accepted Answer · 2012-12-04 11:59:39Z

2

This function computes

3^n where n >= 0

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

answered Dec 4, 2012 at 11:59

tafa

7,3443 gold badges39 silver badges40 bronze badges

Comments

Arsenii Fomin · Accepted Answer · 2012-12-04 11:56:42Z

-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);

answered Dec 4, 2012 at 11:56

Arsenii Fomin

3,3664 gold badges26 silver badges50 bronze badges

5 Comments

John Dvorak Over a year ago

What makes you think this is the desire?

Tom Lilletveit Over a year ago

I have put 3 there just so I can study how the recursive algorithm works and calculates it´s result

mah Over a year ago

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.

Arsenii Fomin Over a year ago

I'm updating several times before final variant, sorry

mah Over a year ago

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?

Collectives™ on Stack Overflow

Tracing simple recursive function

3 Answers 3

2 Comments

Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related