From ASMBits


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.

Sample Input


Sample Output


Write your solution here

Upload a source file...