Javascript Recursion Base Case

I'm sorry I know this is probably not a smart question but it's driving me crazy. Given this recursive function, why is 1 not returned all the time? I mean, eventually the exponent

Solution 1:

The best way to understand is to walk through the code. Let's say you do power(2,3).

What does that do?

2 * power(2,2) 
//Which expands to2 * 2 * power(2,1)
//Which expands to2 * 2 * 2 * power(2,0)
//Which expands to 2 * 2 * 2 * 1

Solution 2:

When 1 is returned, it is not returned to the original function call, but just the most recent function call. Every time the power function calls itself, it puts a new invocation of itself on the stack. So for instance if we call power(2, 1), that will call power(2, 0). power(2, 0) will return its value of 1 to where it was called in power(2, 1). Then power(2, 1) will return base * power(base, exponent - 1); which is base * 1 which is 2.

Solution 3:

This may best be understood by contrasting your recursive power function with a very similar function that does always return the value 1.

function one(base, exponent) {
  if (exponent == 0)
    return1;
  elsereturn one(base, exponent - 1);
}

Notice that the only difference between your power function and one is that the the recursive call to oneis the value being returned in the recursive case.

In your power function, the value being returned is base multiplied with the value of the recursive call. Thus each recursive call to power contributes to the value ultimately being returned by the initial call; whereas, only the final call to one (when exponent is 0) contributes to the returned value.

Solution 4:

Let's assume we call power(2, 5) [i.e. with base=2 and exponent=5]. It will evaluate in the following way:

power(2, 5) = ...

Hmmm... Let's calculate power(2, 5). Is exponent==0? No it isn't (it's 5). Then we return base*power(base, exponent-1), which actually means 2*power(2,4).

power(2, 5) =2*power(2, 4)
            =2* ?

Hmmm... Let's calculate power(2, 4). Is exponent==0? No it isn't (it's 4). Then we return base*power(base, exponent-1), which actually means 2*power(2,3).

power(2, 5) =2*power(2, 4)
            =2* (2*power(2, 3))
            =2* (2* ?)

Hmmm... Let's calculate power(2, 3). Is exponent==0? No it isn't (it's 3). Then we return base*power(base, exponent-1), which actually means 2*power(2,2).

power(2, 5) = 2 * power(2, 4)
            = 2 * (2 * power(2, 3))
            = 2 * (2 * (2 * power(2, 2)))
            = 2 * (2 * (2 * ?))

Hmmm... Let's calculate power(2, 2). Is exponent==0? No it isn't (it's 2). Then we return base*power(base, exponent-1), which actually means 2*power(2,1).

power(2, 5) =2*power(2, 4)
            =2* (2*power(2, 3))
            =2* (2* (2*power(2, 2)))
            =2* (2* (2* (2*power(2, 1))))
            =2* (2* (2* (2* ?)))

Hmmm... Let's calculate power(2, 1). Is exponent==0? No it isn't (it's 1). Then we return base*power(base, exponent-1), which actually means 2*power(2,0).

power(2, 5) =2*power(2, 4)
            =2* (2*power(2, 3))
            =2* (2* (2*power(2, 2)))
            =2* (2* (2* (2*power(2, 1))))
            =2* (2* (2* (2* (2*power(2, 0)))))
            =2* (2* (2* (2* (2* ?))))

Hmmm... Let's calculate power(2, 0). Is exponent==0? Yes, it is! Then we return 1.

power(2, 5) =2*power(2, 4)
            =2* (2*power(2, 3))
            =2* (2* (2*power(2, 2)))
            =2* (2* (2* (2*power(2, 1))))
            =2* (2* (2* (2* (2*power(2, 0)))))
            =2* (2* (2* (2* (2*1))))
            =2* (2* (2* (2*2)))
            =2* (2* (2*4))
            =2* (2*8)
            =2*16=32

Post Scriptum: You should understand that return <something> specifies result value of the innermost (i.e. the latest) function call (not the outermost, i.e. the oldest).

Solution 5:

Because it is the result of multiplying the base by itself a certain number of times, which is how exponents work. Because base is being multiplied by power(base, exponent - 1) (and power(base, exponent - 1) itself is not being returned), each iteration where exponent is not 0 essentially adds another multiplication of the base onto the result.

As an aside, this is not a very good power function.