In 1202 the Italian mathematician Leonardo of Pisa, later nicknamed Fibonacci, put a puzzle in his book Liber Abaci. A pair of rabbits produces a new pair every month, starting in their second month. How many pairs are there after a year? Each month you still have all of last month's rabbits, because none die. You also get one new pair for every pair that was alive two months ago, because those are now old enough to breed. That is exactly "add the two before".
Indian poets had found the same numbers centuries earlier. Virahanka, around 700 AD, counted the rhythms that fill a line using short and long syllables. A short beat takes 1 unit and a long beat takes 2. The number of ways to fill n units follows the same rule. This is the same count as "how many ways to climb n stairs taking 1 or 2 steps", which you will meet as 4.23.1 Climbing Stairs.
Way 1 — The recursion that copies the definition
The definition says F(n) = F(n-1) + F(n-2). Code can say the same thing.
python
def fib_naive(n: int) -> int: if n < 2: return n # F(0) = 0, F(1) = 1 return fib_naive(n - 1) + fib_naive(n - 2)print(fib_naive(10)) # → 55
It is correct and it reads like maths. It is also terribly slow. fib_naive(40) takes many seconds. fib_naive(100) would not finish in your lifetime.
Draw the calls for fib_naive(5). Each call starts two more calls, until it reaches 0 or 1.
Every call for F(5). The amber F(3) is worked out twice from scratch, and the green F(2) three times. The tree for F(n) roughly doubles with each step up in n.
The same small values are worked out again and again. Nothing remembers an answer once it is found. For F(5) the tree has 15 calls. For F(30) it has about 2.7 million. For F(40), about 330 million.
How fast does the tree grow? The number of calls for n is the calls for n-1, plus the calls for n-2, plus 1 for the call itself. That is the Fibonacci rule again. So the call count grows like the Fibonacci numbers themselves. Each Fibonacci number is about 1.618 times the one before it. That number, \varphi \approx 1.618, is called the golden ratio. So the time is about O(1.618^n). Each step up in n multiplies the work by 1.6. This is exponential time, the worst kind of growth you will see in everyday code. 4.1 explains growth rates in full.
The fix is to write down each answer the first time you compute it. Next time, look it up. This is called memoisation, from "memo", a note to yourself.
python
def fib_memo(n: int, memo: dict[int, int] | None = None) -> int: if memo is None: memo = {} # (1) if n < 2: return n if n in memo: return memo[n] # (2) memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo) # (3) return memo[n]print(fib_memo(50)) # → 12586269025
(1) Create a fresh notebook for each top-level call. Writing memo={} directly in the function header is a common Python mistake. That dictionary is created once, when the function is defined, and shared by every call forever.
(2) Already computed? Return the stored answer. No more calls.
(3) Compute it once and store it.
Now each F(k) from 2 to n is computed exactly once. Every later request is a lookup. That makes it O(n) time. It still uses O(n) memory, for the notebook and for the recursion depth. Because of the depth, fib_memo(5000) still hits Python's recursion limit.
Python has this built in. Put @functools.cache above the naive function, and Python keeps the notebook for you.
python
from functools import cache@cachedef fib_cached(n: int) -> int: return n if n < 2 else fib_cached(n - 1) + fib_cached(n - 2)print(fib_cached(80)) # → 23416728348467685
Look at what the computation really needs. To get the next number, you only need the last two. Everything older can be thrown away. So start at the bottom and walk up, keeping just two values.
python
def fib(n: int) -> int: a, b = 0, 1 # (1) a = F(0), b = F(1) for _ in range(n): a, b = b, a + b # (2) return a # (3)print(fib(10)) # → 55print(fib(90)) # → 2880067194370816120print([fib(i) for i in range(12)])# → [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
(1)a holds the current number and b holds the next one.
(2) Move one step forward. The new current is the old next. The new next is the sum of the two. Both right-hand values are computed from the old pair before anything is stored. Writing a = b and then b = a + b on two lines would be a bug, because a would already have changed.
(3) After n steps, a holds F(n).
Trace for n = 5:
step
a
b
start
0
1
1
1
1
2
1
2
3
2
3
4
3
5
5
5
8
F(5) = 5. This is O(n) time and O(1) memory. No recursion, no notebook. It is the answer to give.
Printing the series is the same loop with a print inside.
python
def fib_series(n: int) -> list[int]: out, a, b = [], 0, 1 for _ in range(n): out.append(a) a, b = b, a + b return outprint(fib_series(10)) # → [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
The simple way: generate Fibonacci numbers until you reach or pass the target.
python
def is_fib(x: int) -> bool: a, b = 0, 1 while a < x: a, b = b, a + b return a == xprint(is_fib(21), is_fib(22)) # → True False
Fibonacci numbers grow by about 1.6 times each step. So reaching x takes only about \log_{1.6} x steps, around 90 steps for numbers near 10^{18}.
There is also a test with no loop. A number x is a Fibonacci number exactly when 5x^2 + 4 or 5x^2 - 4 is a perfect square. This was proved in 1972 by Ira Gessel. Check 8: 5 \times 64 + 4 = 324 = 18^2. Yes. It is a fun fact to mention, but the loop is easier to get right.
python
from math import isqrtdef is_fib_formula(x: int) -> bool: def square(k: int) -> bool: return k >= 0 and isqrt(k) ** 2 == k return square(5 * x * x + 4) or square(5 * x * x - 4)print(is_fib_formula(8), is_fib_formula(9)) # → True False
math.isqrt gives the exact whole-number square root. It is safe for huge numbers, unlike math.sqrt, which uses decimals and can be slightly off.
There is an even faster O(\log n) method using matrix powers. It matters only for enormous n with answers taken modulo a number. Knowing it exists is enough for these rounds.
These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.
"How slow is the simple recursive version?" Exponential. Each step up in n multiplies the work by about 1.6. fib_naive(40) already makes over 300 million calls. The cause is that the same small values are worked out again and again.
"How do you make it fast?" Two ways. Memoisation stores each answer the first time it is found, so nothing is computed twice. Or walk forward with two variables, a and b, which is O(n) time and needs almost no memory.
"How much memory does the recursive version use?"O(n). The call tree is huge, but only one path from the top to the bottom is open at any moment. That path is n calls long.
"Why not write memo={} in the function header?" Python creates that dictionary only once, when the function is defined. Every later call shares the same dictionary. That habit causes bugs in other functions, so avoid it.
One thing to volunteer: "This is the simplest example of dynamic programming. Memoisation is the top-down way, and the two-variable loop is the bottom-up way."
Next:4.0.9 Number Systems. Decimal to binary and back, any base, and turning a string into a number without int().