function power(base, exponent) {
if (exponent == 0)
return 1;
else
return base * power(base, exponent - 1);
}
I think that I understand the basic principle of recursion, it simply means you are calling the function within the function itself. This can be used to perform a loop of sorts, but what I cant figure out is how the above code actually decides to loop in order to figure out the exponential value of a number. I used function power(2,5) as my argument and the function knew the answer was 32, but how? Does the function loop itself subtracting 1 from the exponent each time, and multiplying base * base until exponent reaches zero? And if thats the case, how does calling the power function within the function acplish this exactly? And once exponent reaches zero, wouldnt the function then just return 1 and not the correct answer?
function power(base, exponent) {
if (exponent == 0)
return 1;
else
return base * power(base, exponent - 1);
}
I think that I understand the basic principle of recursion, it simply means you are calling the function within the function itself. This can be used to perform a loop of sorts, but what I cant figure out is how the above code actually decides to loop in order to figure out the exponential value of a number. I used function power(2,5) as my argument and the function knew the answer was 32, but how? Does the function loop itself subtracting 1 from the exponent each time, and multiplying base * base until exponent reaches zero? And if thats the case, how does calling the power function within the function acplish this exactly? And once exponent reaches zero, wouldnt the function then just return 1 and not the correct answer?
I consider each recursive step (the function calling itself) producing a shorter and easier problem.
The easiest problem is power(base, 0), which satisfies exponent == 0 and returns one (any base to the zeroth power is 1).
Then, notice that no matter how large exponent is, it is reducing exponent by one, guaranteeing that it will eventually reach the "easiest" problem where the exponent is zero. It only can't be negative, or else this "base case" is never reached.
So, 2^5, or power(2, 5), bees 2 * 2^4. And 2^4 = 2 * 2^3. By continuing this expansion, we get 2 * 2 * 2 * 2 * 2 * 1, which equals 32. The 1 represents the case exponent == 0 being true.
The putation has to keep track how many of these multiplications it has accumulated, and once the base case of exponent == 0 is reached, multiply all numbers together. It cannot know in advance with certainty what power(base, exponent-1) will return.
Follow the call pattern.. Let's assume we do power(2,2).. You get this:
power(2,2) -> (exponent != 0) 2 * power(2, 1)
2 * power(2, 1) -> (exponent != 0) 2 * power(2, 0)
2 * 2 * power(2,0) -> (exponent == 0) 1
2 * 2 * 1 = 4
The way it works is basically your call stack, as long as you keep calling sub-methods, your parent doesn't return. So it keeps nesting itself until it hits a concrete # -- in this case, 1, then it goes back up the stack actually doing the *.
This shows intermediate results which may help you to follow the logic:
Each level has its own value of base, exponent, answer.
function power(base, exponent) {
var answer; // local
level = level + 1;
console.log("Entering: power(" + base + ", " + exponent +
") (level " + level + ")");
if (exponent == 0) { // don't recurse any more
answer = 1; }
else { // recurse to get answer
answer = base * power(base, exponent - 1); }
// now return answer
console.log("Leaving: power("+ base + ", " + exponent +
") (level " + level + ") ans=" + answer);
level = level - 1
return answer;
}
var level = 0; // global
console.log("Final answer: " + power(2, 5));
The best way to explain the above recursive is to see what the console returns
function power(base, exponent) {
// termination/base case
if (exponent == 0)
return 1;
// recursive case
else
console.log(base + ':' + exponent)
return base * power(base, exponent - 1);
// 2 * (2, 4) = 4
// 4 * (2, 3) = 8
// 8 * (2, 2) = 16
// 16 *(2, 1) = 32
// 16 *(2, 0) = 1 recursive stops and returns 1
// function calls the last return = 32
}
var result = power(2,10)
console.log(result)
I hope this give you a more visual view of how this recursive works
This also confused heck out of me when i first saw it, after 10 minutes starring at it, it just came to me....nothing magical....
function power(base, exponent) {
if (exponent == 0)
return 1;
else
return base * power(base, exponent - 1);
}
console.log(power(2, 5));
this is how it runs through:
return base * power(base, exponent - 1)
looking at the above line itself, I was lost too. there are no operations(+,-,*,/,%) done to the given parameters 2 and 5, but somehow at the end, console.log just know to produce correct number.
Because it does not return a numeric value, it simply returns base * power(base, exponent -1) itself, when program reaches power(base, exponent -1), it executes it before return happens, until exponent == 0 bees true.
1st: return base * power(base, 5 - 1);
2nd: return base * base * power(base, 4 - 1);
3rd: return base * base * base * power(base, 3 - 1);
4th: return base * base * base * base * power(base, 2 - 1);
5th: return base * base * base * base * base * power(base, 1 - 1);
6th: return base * base * base * base * base * 1;
because if (exponent == 0) return 1
so: 2*2*2*2*2*1 = 32