Lesson 11 — Fibonacci

Fibonacci: build each value from the previous two

The Fibonacci sequence starts 0, 1, and every next number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8… The efficient way is to keep only the last two values, a and b, and slide them forward each step.

x, y = 5, 7
x, y = y, x       # now x=7, y=5: both change at once
x, y = y, x * y   # now x=5, y=35

The simultaneous assignment is important: both new values are computed from the old a and b.

Why it matters: this "keep a small window of previous results" idea is the seed of dynamic programming (Lesson 20).