I have the following example of a recursive function, and what I don't understand is the order in which things are happening:
function power(base, exponent) {
if (exponent == 0)
return 1;
else
return base * power(base, exponent - 1);
}
When does the function return the values, at the end of all the process or each time?
A simple way to visualize what happens in recursion in general is this:
I.e. if base=5 and exponent=3, the call stack is (last element on top):
5*(5*(5*1))
5*(5*(5*power(5, 0)))
5*(5*power(5, 1))
5*power(5, 2)
power(5, 3)
then every called function has real parameters and is ready to return a value (first element on top):
5*(5*(5*1))
5*(5*5)
5*25
125
Note that here the functions are calulated in inverse order: first power(5, 0), then power(5, 1), and so on.. After each calulation an element of the stack is released (i.e. memory is freed).
Hope it helps :)
power(3,3) and puts on the stack the first return 3 * power(3,2); and then 3 * power(3,1); until it meets the stop condition, which is a final number and not another function, and calculates all the function in the stack from to to bottom?
It is generally helpful in understanding recursive functions such as this to work things out like you would in an algebra class. Consider:
power(3, 4)
= 3 * power(3, 3)
= 3 * (3 * power(3, 2))
= 3 * (3 * (3 * power(3, 1)))
= 3 * (3 * (3 * (3 * power(3, 0))))
= 3 * (3 * (3 * (3 * 1)))
= 3 * (3 * (3 * 3))
...
= 81
https://www.youtube.com/watch?v=zg-ddPbzcKMThe key here is that power is calling itself exactly in the way it could call any other function. So when it does that, it waits for the function to return and uses its return value.
So if you do
var x = power(10, 2);
Your call to power will get to this line:
return base * power(base, exponent - 1)
...and call power(10, 1), waiting for that to return.
The call to power(10, 1) will, of course, get to the line:
return base * power(base, exponent - 1)
...and call power(10, 0), waiting for that to return.
The call to power(10, 0) will return 1, which is then used by the call in #2 above to complete its work and return 10 * 1 = 10, which will then let your original call in #1 above return the value 10 * 10 = 100.
When seeking to understand things like this, there's nothing quite like walking through the code with a debugger. In this modern world, you have plenty to choose from, many of which may already be on your computer.
For better visualization, just substitute the function call with the function body (may be pseudo code for instance).
function power(base, exponent) {
if (exponent == 0)
return 1;
else
return base * power(base, exponent - 1);
}
power(5, 3) expands to this
function power(5, 3) {
// exponent 3 is not 0
// return 5 * power(5, 3-1)
return 5 * function power(5, 2) {
// exponent 2 is not 0
// return 5 * power(5, 2-1)
return 5 * function power(5, 1) {
//exponent 1 is not 0
// return 5 * power(5, 1-1)
return 5 * function power(5, 0){
//exponent 0 is 0
return 1;
}
}
}
}
Now the picture is clear. It all becomes like below..
// 1
function power(5, 3){
return 5 * function power(5, 2){
return 5 * function power(5, 1){
return 5 * ( function power(5, 0){
return 1;
} )
}
}
}
// 2
function power(5, 3){
return 5 * function power(5, 2){
return 5 * ( function power(5, 1){
return 5 * 1;
} )
}
}
// 3
function power(5, 3){
return 5 * ( function power(5, 2){
return 5 * 5 * 1;
} )
}
// 4
function power(5, 3){
return ( 5 * 5 * 5 * 1 );
}
// 5
5 * 5 * 5 * 1;
As with any recursive function, the return from a particular "instance" happens when the return value has been calculated. This means that the recursed versions will then have been calculated.
So if you pass in an exponent of 4, there will be at some point 4 copies of the function being executed at one time.
This line and its resolution really trips me up:
return base * power(base, exponent - 1)
I get that the exponent is decremented until it meets the base case, but when you mulitply the base times the recursive function call, I keep thinking "how does the function mulitply the base by itself(the base arguement)?", where is it doing that exactly, because calling base * power(base, exponent - 1) doesn't look like the standard loop contruction. How can it be calling a function with two arguements, how does it know to skip the exponent arguement and multiply the base by the base?
From a mathematical perspective:
let x = base, let n = exponent
x*x^(n-1) = x^n
because
x^1*x^n-1=x^n (exponents of like term adds together)
It is the same as:
base * base*exponent-1.
console.log(base,exponent). All shall be revealed!printf-style debugging has little place in 2011! :-)powerfunction will fail if passed a negative exponent. It will repeatedly call itself with lower and lower negative exponents until it reaches the recursion limit and bails with a "Too much recursion" error. In some other environments, we know that by another name: stack overflow! ;-)