The Fibonacci sequence can be defined recursively. The nth Fibonacci number is the sum of the (n-1)th and (n-2)th Fibonacci number. There are two base cases: The 0th and 1st Fibonacci number are both 1.
Suppose you computed the nth Fibonacci number directly using the above recursive formulation (no other optimizations or memoization, etc). How many calls to the function fib are required? For example, fib(2) requires 3 calls: fib(2) counts as one call, and it calls fib(1) and fib(0), both of which are base cases that don't call further functions.
Write a function that computes the number of calls to fib required to compute the nth Fibonacci number if the algorithm were implemented recursively.
unsigned int numfib(unsigned int n);
n will be no greater than 30, to keep execution time reasonable.
Expected solution length: Around 25 lines.
Write your solution here