Trey Hunner 🐍 on Nostr: Fibonacci is similar. The recursive version: def fibonacci(n): if n <= 1: return 1 ...

Fibonacci is similar.

The recursive version:

def fibonacci(n):
if n <= 1:
return 1
return fibonacci(n-1) + fibonacci(n-2)

And the iterative version:

def fibonacci(n):
a = b = 1
for _ in range(n-1):
a, b = b, a+b
return a

But here, the recursive version is actually MUCH worse: it turns an O(n) computation into an O(2ⁿ) one: https://pym.dev/p/3b2bt/

🧵 (4/6)