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.
Write a function that computes the value of the nth Fibonacci number.
unsigned int fib(unsigned int n);
You may assume that the input will be small enough to run in a reasonable amount of time when implemented using recursion. (The execution time budget is approx 40 instructions per call to fib, if implemented recursively.)
Expected solution length: Around 15-20 lines.
Write your solution here