Hello, I thought the programming gurus in this forum could lend me a hand understanding recursion in Javascript. I'm following an online Javascript tutorial ("Eloquent Javascript", I recommend it to anyone) and chapter 3 shows this function:

``````function power(base, exponent) {
if (exponent == 0)
return 1;
else
return base * power(base, exponent - 1);
}``````

I got as far as understanding that the function it's calling itself, with the exponent being lesser and lesser, until it's 0, when at that point it returns 1 which makes it multiply the base by 1 and it ends.

So what it does is multiply the base by itself as many times as the exponent tells.

What I don't get is... why does "power(base, exponent - 1)" return the base to be multiplied again by itself? In my mind this should... well do nothing and just call itself until exponent is 0.

And... where is it storing every multiplication? For instance for power(2,3) the first result is '4', where is that number "stored" to be multiplied the next time by 2 again?

I started firebug and followed the script step by step and found something weird: the execution follows the logical flow of the program, it jumps from the call to the function itself for exponent values 3,2,1,0 at which point assigns the value 1 and then the strange thing is that it executes:

return base * power(base, exponent - 1);

as many times as the exponent. Three times for power(2,3), one after the other. So it seems Javascript is doing the calculations at the end?

3
Contributors
8
Replies
9
Views
8 Years
Discussion Span
Last Post by ~s.o.s~

The values are being kept and passed on function argument variables base & exponent, and the function will call itself until the exponent variable value reaches 0 ending the loop with 1.

Such a small, simple and powerful code deserves admiration :')

But "base" is always 2. The values passed are:

2 - 3
2 - 2
2 - 1
2 - 0

of course, "base" argument-value is always the initial given value - according to the function: only the "exponent" should change!
"base" is the BASE! There's no practical use if the base number changes.

Ok, but, at some point there is the result '4' that will be multiplied by '2' in the next iteration... what I don't see is where is that '4'?

When you say that "base" is the BASE, do you mean the Base Case? As I understand it, the Base Case would be 0, which makes the recursion stop?

Edited by Altairzq: n/a

*I mean the Base Case would be when exponent = 0.

omg I got it lol. Now I can go to sleep :zzz:

And probably tomorrow will have lost it again :p

According to what is written in the code - the function recursion should stop only when "exponent" reaches 0 value.

so if the base number is 2, on exponent 7, in iterations we'll have:
2 * (7 - 1) = (2 * 6) = 12
2 * (6 - 1) = (2 * 5) = 10
2 * 4 = 8
2 * 3 = 6
2 * 2 = 4
2 * 1 = 2
2 * 0 = 0
conditional met 0 ... ... ... ... the function will stop returning
0 = 1
1 meaning "true" the function finished operation.

``````power(2, 3) =>

- 2 * power(2, 2)
- 2 * (2 * power(2, 1))
- 2 * (2 * (2 * power(2, 0)))
- 2 * (2 * (2 * 1))
- 2 * (2 * 2)

= 8``````

The trick here is to force the repetition of `base' for an `exponent' number of times by using recursion.

Edited by ~s.o.s~: n/a