Fibonacci Calls

Question

The ’fib’ function returns the $n^{th}$ Fibonacci number if called using ’$fib(n)$’ Suppose calling ’$fib(n)$’ requires G(n) calls to the ’fib’ function in total, because of recursion Prove that $G(n) = G(n − 1) + G(n − 2) + 1$

Workings:

It would take $G(n-1)$ calls to call $fib(n-1)$ Fibonacci number and $G(n-2)$ calls for $fib(n-2)$ Fibonacci number and then 1 more call (FOR SOME REASON). Summing these up gives $G(n)$.

Is my thinking correct and what would the 1 call be for.

Answer 1

The +1 'call' is the addition itself.

Answer 2

This is more of a programming question than a math one.

But what does the fib function really does ? it adds up two numbers.

So when you call fib(n), it computes fib(n-1), fib(n-2) and then add them up.

Maybe you can try and pseudo code fib() to get a better grasp of it, good luck =)

EDIT : As a side note, fib sequence is a traditional but very poor first example when you learn about recursive functions simply because there's betters ways to compute fib numbers. If you want to get a better example, look at "flood fill" algorithms.