Why is the answer, 13 as given. I just cannot get my head around it.
What does the following function return, if the given input is 7:
function foo($bar) {
if ($bar == 1) return 1;
elseif ($bar == 0) return 0;
else return foo($bar - 1) + foo($bar - 2);
}
Correct Answer: D. 13
nneonneo should have just posted his comment as the answer, but, this is is how the concept of recursion works:
foo(7) = foo(6) + foo(5)
But wait, what're those equal to?
foo(6) = foo(5) + foo(4)
Sonofagun!
foo(5) = foo(4) + foo(3)
Hmm .. a pattern emerging ..
foo(4) = foo(3) + foo(2)
foo(3) = foo(2) + foo(1)
foo(2) = foo(1) + foo(0)
foo(1) = 1
and
foo(0) = 0.
So now you can figure out backwards back to the values, but (and this the more important question) what's really happening when you increase $bar by 1 again?
How does foo(8) compare to foo(7)?
And the answer is that foo (8) equals foo(7) + foo(6). In other words, it is equal to 13 + 8 - the sum of the two previous outputs of foo .. hey, that sounds familiar ... is there some famous sequence that is equal to the sum of the previous two numbers?
1, 2, 3, 5, 8, 13 ...
That's right, this is how you can calculate the Fibonacci sequence recursively. And if you think about how you build up the Fibonacci sequence, it's really
1, 1 + 1, 2 + 1, 3 + 2, 5 + 3, 8 +5
Which is just
1, 1 + 1, (1 + 1) + 1, (2 + 1) + (1 + 1), etc.
By "seeding" the initial values (position "0" is 0, position 1 is 1) and then adding them together, you are able to derive each number in the sequence using just the original seeds and a lot of addition.
So in this case, bar represents the bar position in the Fibonacci sequence. So the 7th number in the sequence is 13.
It is very simple, just trace the sequence by hand. When using this type of recursion it helps to think of it more as a mathematical function than a programming procedure. If you want to get to know it more naturally, playing with a functional language *ML or some LISP would help you a lot and very quickly. When you have a recursion on a data structure (Stack/Queue), then it is a bit different, but functional programming experience helps for that too.
foo(0) = 0
foo(1) = 1
foo(2) = foo(1) + foo(0) = 1 + 0 = 1
foo(3) = foo(2) + foo(1) = 1 + 1 = 2
foo(4) = 2 + 1 = 3
foo(5) = 3 + 2 = 5
foo(6) = 5 + 3 = 8
foo(7) = 8 + 5 = 13
foo(7) -> foo(7-1) + foo(7-2).else { $ret = foo($bar - 1) + foo($bar - 2); echo "returning $ret<br>"; return $ret; }