The Fibonacci sequence starts with 0 and 1. Every number after that is the sum of the two numbers before it.
That gives 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 and onward. Step through it below. The yellow box is the number being calculated. The two grey boxes are the numbers it is built from.
A position is not a value
Look at the two kinds of number in Figure 1. The small number above each box is a position, n. The number inside the box is the value stored there, F(n). At position 6 the value is 8. The rule adds the values at positions 5 and 4, which are 5 and 3. It does not add 5 and 4.
This is the most common mistake when writing Fibonacci as a recursive function. n - 1 is a position. fibonacci(n - 1) is the value at that position. Mix them up and the code runs without errors, but gives wrong answers from F(3) on.
Wrong: adds a position
def fibonacci(n): if n == 0: return 0 if n == 1: return 1 return (n - 1) + fibonacci(n - 2)
fibonacci(3) = (3 − 1) + fibonacci(1) = 2 + 1 = 3. The right answer is 2.
Right: adds two values
def fibonacci(n): if n == 0: return 0 if n == 1: return 1 return fibonacci(n - 1) + fibonacci(n - 2)
fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2.
A useful habit: before you write the recursive line, ask what the call on the smaller input returns. Then build your answer only from those returned values.
Why two starting numbers?
Each new number needs two earlier ones. So the rule can't produce the first two numbers by itself, and they have to be given.
In code, those are the base cases: n == 0 and n == 1. Any other n eventually reaches one of them, because each call moves down by 1 or 2. A third base case for n = 2 isn't needed. F(2) = F(1) + F(0) already works.
Numbers as squares
Draw each Fibonacci number as a square with that side length. Put a 1 next to a 1, a 2 along their shared edge, a 3 beside those, then a 5, then an 8. Every new square fits the long side of the rectangle exactly. That's because the long side is the previous two sides added together, which is the Fibonacci rule again. Quarter-circle arcs through each square give the familiar spiral.
How fast it grows
Divide each number by the one before it. The early ratios swing about: 1, 2, 1.5, 1.667, 1.6. Then they close in on one value, about 1.618. That is the golden ratio, written φ (phi).
A steady ratio means steady multiplication. Once the sequence gets going, each number is about 1.6 times the one before it, so the values grow exponentially. It takes only 30 steps to pass 800,000.
Where it comes from
Leonardo of Pisa, later called Fibonacci, published the sequence in Europe in his 1202 book Liber Abaci. He used it to answer an idealised puzzle about breeding rabbits. Each month, every adult pair produces a new pair, and a newborn pair takes a month to mature. This month's pairs equal last month's pairs, plus one newborn pair for every pair that was alive two months ago. Indian scholars studying the rhythms of Sanskrit poetry had counted the same numbers centuries earlier, including Virahanka and later Hemachandra.
The numbers also show up in plants. The spirals in a sunflower head or on a pinecone often come in two sets whose counts are neighbouring Fibonacci numbers, such as 34 and 55.
Why programmers meet it early
The definition is already recursive: a number defined in terms of smaller cases of itself. That makes it the standard first exercise in recursion. It also makes a good next question. The code above is correct, but how many calls does fibonacci(5) make? Draw the calls as a tree and count them. That count leads straight to the next topic: the gap between code that is correct and code that is fast.