# A recursion question

This came from a question on another forum

The code’s a bit like this

``````function f(n){
if ( n == 1 || n == 2 ) { return n; }
else { return (f(n-1)+f(n-2));}
}
``````

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

``````

Thanks

RLM

I would have edited my post.

Just to say that I’m not looking for an explanation of Fibonacci formula.

I’m more interested in how the two function calls return (fn()+fn()) are processed in the recursion.

Thanks

RLM

I think you’re looking for more of a “how does recursion work” answer?

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

``````
return 5 + f(n-2);

``````

Then after the right side call is finished

``````
return 5 + 3;

``````

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
``````

RLM

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);

``````

crmalibu,

That’s excellent. Thank you.

I can already see one flaw in my logic.

I’ll have a good look at your output and see if I can get it into my thick skull.

Thanks again.

RLM