Getting Started With the Fibonacci Sequence

00:00 Getting Started With the Fibonacci Sequence. Leonardo Fibonacci was an Italian mathematician who was able to quickly produce an answer to this question asked by Emperor Frederick II of Swabia: “How many pairs of rabbits are obtained in a year, excluding cases of death, supposing that each couple gives birth to another couple every month and that the youngest couples are able to reproduce already at the second month of life?” The answer was the sequence that you’re seeing on-screen.

00:33 The pattern begins after the first two numbers, zero and one, where each number in the sequence is always the sum of the two numbers before it. Indian mathematicians had known about this sequence since the sixth century, and Fibonacci leveraged it to calculate the growth of rabbit populations.

00:51 F(n) is used to indicate the number of pairs of rabbits present in month n, so the sequence can be expressed as seen on-screen. In mathematical terminology, you’d call this a recurrence relation, meaning that each term of the sequence, beyond zero and one, is a function of the preceeding terms.

01:10 There’s also a version of the sequence where the first two numbers are both one, like so. In this alternative version, F(0) is still implicitly zero, but you start from F(1) and F(2) instead. The algorithm remains the same because you’re always summing the previous two numbers to get the next number in the sequence. For the purposes of this course, you’ll use the version of the sequence that starts with zero.

01:36 Generating the Fibonacci sequence is a classic recursive problem. Recursion is when a function refers to itself to break down the problem it’s trying to solve. In every function call, the problem becomes smaller until it reaches a base case, after which it will then return the result to each intermediate caller until it returns the final result back to the original caller.

02:00 If you wanted to calculate the F(5) Fibonacci number, you’d need to calculate its predecessors, F(4) and F(3), first. And in order to calculate F(4) and F(3), you would need to calculate their predecessors.

02:13 The breakdown of F(5) into smaller sub-problems would look as seen on-screen.

02:23 Each time the Fibonacci function is called, it gets broken down into two smaller sub-problems because that’s how you define the recurrence relation.

02:35 When it reaches the base case of either F(0) or F(1), it can finally return a result back to its caller. In order to calculate the fifth number in the Fibonacci sequence, you solve smaller but identical problems until you reach the base cases, where you can start returning a result.

02:53 The colored sub-problems seen on-screen represent repetitive solutions to the same problem. If you go further up the tree, you’ll find more of these repetitive solutions.

03:04 This means that to generate a Fibonacci sequence recursively, you have to calculate many intermediate numbers over and over. This is one of the fundamental issues in the recursive approach to the Fibonacci sequence. In the next section of the course, you’ll see how to generate the Fibonacci sequence recursively using Python.