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 an efficient (possibly non-recursive) function that computes the value of the nth Fibonacci number. In addition, if the nth Fibonacci number will overflow an unsigned integer, return 0 to indicate an overflow.
unsigned int fib(unsigned int n);
The input will not be small enough to run in a reasonable amount of time if implemented using plain recursion. The input test cases are bigger and have a lower runtime limit than fib1.
Expected solution length: Around 20 lines.
Write your solution here