(VERY simple recursion) what am I missing?

Question

I can't see what I am missing in this recursion call...

var power = function(b, e)
{
    if (e===0)
    {
       return 1;
    }
    else
    {
       return b*power(b, e-1);
    }
};

The first if statement is for catching numbers to the zero power (those always equal 1). But it's also the base case, so when e (exponent) reaches 0 the function exits and leaves me with the correct answer.

How is this returning the correct number and NOT the number 1? Every time, e is getting down to 0, but it returns the correct answer and NOT 1. Sorry I'm a noob, but I'm so confused...

Good question, I wasn't able to see the answer at first, either! — Ethan Parker, Apr 03 '14 at 17:47

score 4 · Answer 1 · answered Jun 20 '12 at 22:41

4

You have a recursive function, when it "returns 1" it then goes back up through the stack frames and multiplies 1 by all the other b variables it has stacked up. 1*b*b*b... etc.

1*anything is the identity function. It returns itself, not 1.

answered Jun 20 '12 at 22:41

TheZ

3,663
19
34

score 2 · Answer 2 · edited May 23 '17 at 12:21

Lets say you do power(2,4), it will go into the else and return 2 * power(2, 3). Before it can return, it has to evaluate the expression it's returning, so it does power(2, 3).

This goes into the else again to return 2 * power(2,2). Same deal here, it has to evaluate the expression. You keep doing this until you get to your base case where it simply returns 1. Now you go to the 2nd-from-bottom level and that can return because it will just be 2*1, so it goes to the next higher level, which will be 2*2*1 and so on until it gets to the top most level and gives you your answer.

See this SO (same question) for more explanations.

Great! thanks for the help! Sorry this was a duplicate question, I'm brand new to stack overflow.... I'l try to search better in the future. — erparker, Jun 20 '12 at 22:58

score 1 · Answer 3 · answered Jun 20 '12 at 22:41

1

On the stack, you'll have 1*b*b*b*b... e times. When the base case hits, the stack unwinds and you get the correct answer.

answered Jun 20 '12 at 22:41

gcochard

11,408
1
26
41

score 1 · Answer 4 · answered Jun 20 '12 at 22:48

1

Here is an execution example:

power = function(2, 2)

2 is different of 0, then return 2*function(2, 1)
   -> 1 is different of 0, then return 2*function(2, 0)

           -> 0 equal 0 return 1

   -> return 2*1
return 2*2*1

power = 4

answered Jun 20 '12 at 22:48

Zonata

471
2
6
20

(VERY simple recursion) what am I missing?

4 Answers4