# Different Functions, Same Output

The two functions shown below compute the $$n^\text{th}$$ Fibonacci number.

For large values of $$n$$, one of the functions is significantly faster than the other. Which function is faster, fib1 or fib2?

 1 2 3 4 5 6 7 8 9 def fib1(n): if n == 0: result = 0 elif n == 1: result = 1 else: result = fib1(n - 1) + fib1(n - 2) return result 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 def fib2(n): if n == 0: result = 0 elif n == 1: result = 1 else: a = 0 b = 1 for i in xrange(0, n - 1): result = a + b a = b b = result return result 
×