fibonacci numbers, why does this recurring function work?

Question

I'm going through a programming book and one of the examples is about fibonacci numbers, and how a recurring function finds the fibonacci number for the nth one along.

The code looks like this:

Int fib (int n)
{
If (n<3)
Return (1);
Else
Return (fib(n-1))+(fib(n-2))
}

Now this isn't exact because I'm typing from my phone and I have a understanding how the code is working, it's calling itself until it returns 1, then it's adds up the return values until you have the correct fibonacci number for the position in the sequence.

So I don't need help with the code. What I do need help with is understanding why this works. How does adding all the returns give the correct answer?

Please can someone explain why this is working. Thanks. It's driving me mad.

Answer 1

Recursion is like this:

1. A child couldn't sleep, so her mother told her a story about a little frog,
2. who couldn't sleep, so the frog's mother told her a story about a little bear,
3. who couldn't sleep, so the bear's mother told her a story about a little weasel...
4. who fell asleep.
5. ..and the little bear fell asleep;
6. ...and the little frog fell asleep;
7. ...and the child fell asleep.

source