Help in Understanding Recursion

Help in Understanding Recursion
0.0 0
#1 
function power(base, exponent) {
debugger;
  if (exponent == 0)
    return 1;
  else
	var b = power(base, exponent - 1);
    return base * b;
}

console.log(power(2, 3));
// → 8

So I am using the Chrome Dev Tools to try and peek into what is happening here and still cannot quite grasp it. I have assigned var b to power(base, exponent - 1); instead of just having it run in the else statement because I wanted to view the VALUE of that function being run.

Not sure if this is even explainable over a forum post, but I am trying to really grasp the WHY and the WHAT of what is happening in this basic recursion example.

I can see that this function loops through subtracting 1 from the exponent each time until it gives me the answer, but I don’t see where the values are stored, or where the browser is getting the information to do its math.

Please excuse my lack of wording and understanding to correctly phrase this problem I am having.

#2

Pythontutor is a great website to see the execution of a function step by step,
I’ve created one for you where you can inspect it here:

https://goo.gl/7RDQDY

That said here’s how your function develop assuming you called power(2, 3)

Basically being power a function that call itself, each return wait for the next one to be resolved so you have:

step 1

base: 2
exponent: 3
b: undefined

base: 2
exponent: 2
b: undefined

base: 2
exponent: 1
b: undefined

base: 2
exponent: 0
b: undefined
return: 1 // here we hit our first return since we got the exponent = 0 condition

From here on the return statements starts to “chain up” where b won’t be undefined no more:

step 2

base: 2
exponent: 3
b: undefined

base: 2
exponent: 2
b: undefined

base: 2
exponent: 1
b: 1 // value returned from prev function
return: 2

All the way up to the first time you called power

Hope it makes sense :slight_smile:

#4

What I am confused about is where the multiplying the base * exponent actually happens.

I see that the base will eventually be multiplied by the return of 1, once the exponent == 0. Once that happens however, what is telling this function to continue to multiply the base * return value.

Also, I tried the link you sent but it times out, giving me an error.

#5

I think I’ve got it! I made a program flow chart, does this seem correct?

image
image.jpg746x767 53.8 KB

#6

That’s exactly what happens, your power keeps creating itself until it reaches a return, and from there start to chain it back to the starting point :slight_smile: