Elegant, but inefficient if you want to get exact values for large n. You're much better off using doubling operations. If you forget those, you can remember them from the matrix version. If fib(0) = 0. fib(1) = 1. etc. Then
n
[0 1] = [fib(n) fib(n+1)]
[1 1] [fib(n+1) fib(n+2)]
With repeated squarings, you can efficiently generate any Fibonacci number you want.
Here (where you have to search through Fibonacci numbers) I suspect memoization is rather the way to go:
# memoized fibonacci function
fibtable = {1:1, 0:1}
def fib (n):
global fibtable
if n in fibtable.keys():
return fibtable [n]
val = fib (n-1) + fib (n-2)
fibtable [n] = val
return val
