I tried to breakdown what happens in the recursion here.
I’m interested to know how the process works exactly and
wondered if someone here would be kind enough to explain.
var stack = true;
function f(n, fn){
if (stack) { console.log ("n = "+n+" and passed from "+fn); }
else if (!stack) { console.log ("n = "+n+" and popped from stack f(n-2)"); }
if ( n == 1 || n == 2 ) {
console.log ("condition met ( n == 1 || n == 2 ). return "+n);
stack = false; return n;
} else {
stack = true;
console.log ("(f(n-1)+f(n-2)) f(n-1) is "+(n-1)+" : f(n-2) is "+(n-2));
return (f(n-1, "f(n-1)")+f(n-2, "f(n-2)"));
}
}
console.log("sequences = "+(f(5, "outside")));
// n = 5 and passed from outside
// (f(n-1)+f(n-2)) f(n-1) is 4 : f(n-2) is 3
// n = 4 and passed from f(n-1)
// (f(n-1)+f(n-2)) f(n-1) is 3 : f(n-2) is 2
// n = 3 and passed from f(n-1)
// (f(n-1)+f(n-2)) f(n-1) is 2 : f(n-2) is 1
// n = 2 and passed from f(n-1)
// condition met ( n == 1 || n == 2 ). return 2
// n = 1 and popped from stack f(n-2)
// condition met ( n == 1 || n == 2 ). return 1
// n = 2 and popped from stack f(n-2)
// condition met ( n == 1 || n == 2 ). return 2
// n = 3 and popped from stack f(n-2)
// (f(n-1)+f(n-2)) f(n-1) is 2 : f(n-2) is 1
// n = 2 and passed from f(n-1)
// condition met ( n == 1 || n == 2 ). return 2
// n = 1 and popped from stack f(n-2)
// condition met ( n == 1 || n == 2 ). return 1
// sequences = 8
I think you’re looking for more of a “how does recursion work” answer?
This page looks pretty good. I think factorial() is a better algorithm to start with, and the good thing about this page is they explain the call stack, and have some images to help you vidualize what’s going on.
They use c code, but
int factorial(int n)
{
return n * factorial(n-1);
}
Is equivalent to
function factorial(n)
{
return n * factorial(n-1);
}
The f() function works similar. But since the recursive case calls the function twice:
return f(n-1) + f(n-2);
The function call on the left happens first. It will recurse fully until all of the nested function calls return, before the right hand side function call will begin. For example, at some point of execution, once the left hand call has returned, you have something like this
Thanks a lot crmalibu, greatly appreciated. I’ve printed off that link you gave me.
First off looking at the sequence of number it was pretty easy to come up with what I think is a better alternative
function f(i){
var a = 0, b = 1, c;
while (i--){ c = (a + b); a = b; b = c; }
return c;
}
Solving for 20 you’ve got 1 function call as opposed to 13,500+ using the recursion method.
Edit: and while i’m at it
function factor(n){
var i = n;
while (--i){ n*= i; }
return n;
}
console.log (factor(6)); //720
Back to the example though. What you say makes sense, but the logged outputs don’t seem to tally with that.
n = 5 and passed from outside
(f(n-1)+f(n-2)) f(n-1) is 4 : f(n-2) is 3
n = 4 and passed from f(n-1)
(f(n-1)+f(n-2)) f(n-1) is 3 : f(n-2) is 2
n = 3 and passed from f(n-1)
(f(n-1)+f(n-2)) f(n-1) is 2 : f(n-2) is 1
n = 2 and passed from f(n-1)
condition met ( n == 1 || n == 2 ). return 2
n = 1 and popped from stack f(n-2)
condition met ( n == 1 || n == 2 ). return 1
n = 2 and popped from stack f(n-2)
condition met ( n == 1 || n == 2 ). return 2
n = 3 and popped from stack f(n-2)
(f(n-1)+f(n-2)) f(n-1) is 2 : f(n-2) is 1
n = 2 and passed from f(n-1)
condition met ( n == 1 || n == 2 ). return 2
n = 1 and popped from stack f(n-2)
condition met ( n == 1 || n == 2 ). return 1
for instance with regards the right hands side I don’t see one console output of n = x and passed from f(n-2)
Yet when you look at the values for n which are popped of the stack/heap LIFO they do appear to tally with the right hand side i.e. 3 2 1 returns 1 2 3
The left hand side only got as far as 2 before it met the base condition/stopper.
What happens to the left hand side f(n-1)'s stacked values? I’m obviously missing something here.
Thanks again
Edit: just a quick experiment
function fn1() { console.log ("I'm fn1"); }
function fn2() { console.log ("I'm fn2"); }
function test(){
for (var i = 0; i < 10; i+=1){ fn1()+fn2();}
}
test();
// I'm fn1
// I'm fn2
// I'm fn1
// I'm fn2
// .
// .
// .
// .
// I'm fn1
// I'm fn2
Recursion is rarely the most cpu/memory efficient way to code an algorithm. But for certain things, the same algorithm expressed recursively is much easier to code/read. Anything you do with a loop, can also be done with recursion(and vice versa).
You not seeing n = x and passed from f(n-2)
has to do with how you maintained your stack variable. It’s flawed.
I’m gonna use indentation in the output to try to make it more clear.
function repeat(str, times) {
return new Array(times + 1).join(str);
}
function log(msg, depth) {
console.log(repeat(' ', depth) + msg);
}
function f(n, depth) {
log("n=" + n, depth);
if ( n == 1 || n == 2 ) {
log("base case", depth);
log("returning " + n, depth);
return n;
} else {
log("recursive case", depth);
log("begin left ", depth);
var left = f(n-1, depth + 1);
log("end left ", depth);
log("begin right ", depth);
var right = f(n-2, depth + 1);
log("end right ", depth);
var result = left + right;
log("returning " + left + "+" + right + "=" + result, depth);
return result;
}
}
f(5, 0);