3 ms·
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
by throwawayiionqz 6y ago
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]
- dotancohen 6y agoYou have a bug for the case of fib(0).
- throwawayiionqz 6y agoIndeed, if you wish the sequence to be defined at 0, eru's solution is better (and appeared earlier while I was typing)