UPDATE: I wrote this post before heading to Chapter 12 of Unit 6, and I just realized that this post contains the answer to the question! So stop readying if you have not attempted!
1, 1, 2, 3, 5, 8, 13, 21 …
Each number is the sum of its two preceding numbers ( 2 = 1 + 1, 21 = 8 + 13).
In every recursive definition, there are two cases, the base case, and the recursive case. The base case is a starting point, which is not defined in itself. This means that it has a value which we already know before any evaluation is done. In the case of the Fibonacci sequence, there are two base cases: the first two 1s. The recursive case is defined in terms of smaller versions of itself, which will repeatedly define in a smaller scope such that it reaches the base case. It will probably be clearly in the code below:
def fib(n): # n is the position of the number in the sequence
if n == 1:
if n == 2:
return fib(n-1) + fib(n-2)
i = 1
while i < 11:
i += 1
The procedure fib() takes in a single parameter n, which is the position of the number in the sequence which you wish to find the value of. If n is 10, it means that you want to find the value of the tenth number in the sequence. Here you can see our base cases very clearly: when the value n is 1 and 2, the value returned is both 1. This means that the first and second number in the sequence is both 1.
If we want to find the third number in the sequence, we pass in n = 3: here is where the magic happens:
- fib(3) is evaluated, and since 3 is neither 1 nor 2, the procedure returns fib(n-1) + fib(n-2), which is fib(2) + fib(1)
- Doesn’t this look familiar, fib(2) is the second number in the sequence, which is 1, and fib(1) is the first number, which is also 1. Hence fib(3) = 1 + 1 = 2! Nice!
So what if we try something like fib(999)? Okay prepare yourself:
- (no just kidding we’ll do fib(5)) fib(5) will return fib(4) + fib(3)
- fib(5) = fib(4) + fib(3)
- fib(4) will return fib(3) + fib(2), fib(3) will return fib(2) + fib(1)
- fib(5) = fib(3) + fib(2) + fib(2) + fib(1)
- fib(3) will return fib(2) + fib(1), and all fib(2) and fib(1) will return 1
- fib(5) = fib(2) + fib(1) + 1 + 1 + 1
- fib(5) = 1 + 1 + 3
- fib(5) = 5!
You can definitely copy the code into python and try a fib(99999), but I think it’ll take a while to complete.