The "better" recursive solution computes fib(n) and fib(n-1) at the same time. Linear time recursion!
def f(n):
if n<=2: return (1, 1)
else:
a, b = f(n-1)
return (b, a+b)
def fib(n):
return f(n)[1]