Javascript Recursion Base Case
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 one
is 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.
Post a Comment for "Javascript Recursion Base Case"