I am at San Francisco right now attending the JavaOne conference. Yesterday I was at the Pavilion and the guys from Amazon had put a brain teaser for everybody. I was the 11th person who answered the teaser correctly. Got a ‘Ninja Coder’ tag and a gift.


Here is the question for you to try.

unsigned int fib(unsigned int n){
if n == 0 return 0
if n == 1 return 1
if n == 2 return 1 // NINJA LINE

return fib(n-1)+fib(n-2)

What would be the difference in the number of times that the fib function is called if the ‘NINJA LINE’ is commented out?
Give the answer as an expression of n.