Fibonacci sequence

Brain teasers

In the 13th century, there lived an Italian mathematician named Leonardo of Pisa. He studied various mathematical concepts including sequences, which he used to illustrate the growth of a hypothetical population of rabbits. The man was widely known as Fibonacci. While he did not discover the sequence itself, he played a crucial role in popularizing it in Europe. The term “Fibonacci sequence” was coined by later mathematicians to honor his contributions to mathematics. Today, Fibonacci’s name is closely associated with this famous sequence and its mathematical properties.

The Fibonacci sequence has many interesting properties and appears in various natural phenomena, such as the arrangement of leaves on a stem, the branching of trees, and the spirals found in seashells and galaxies. It also has applications in mathematics, computer science, and even financial analysis, where it’s used in the calculation of Fibonacci retracements and extensions.

Mathematically, the Fibonacci sequence can be defined recursively as:

• F(0) = 0

• F(1) = 1

• F(n) = F(n-1) + F(n-2) for n > 1

The sequence starts with two initial numbers, typically 0 and 1, and then each subsequent number in the sequence is the sum of the two numbers that immediately precede it. Here is a more detailed explanation:

1. Start with the initial values: 0 and 1.

2. The next number in the sequence is obtained by adding the two previous numbers. So, 0 + 1 = 1.

3. The sequence now looks like this: 0, 1, 1.

4. To get the next number, add the last two numbers: 1 + 1 = 2.

5. The sequence becomes: 0, 1, 1, 2.

6. Continue this process: 1 + 2 = 3.

7. The sequence now looks like this: 0, 1, 1, 2, 3.

8. Adding the last two numbers: 2 + 3 = 5.

9. The sequence becomes: 0, 1, 1, 2, 3, 5.

10. And so on...

The sequence continues infinitely, producing numbers like 8, 13, 21, 34, 55, and beyond.

We are ready to state the problem:

Given a positive integer number, write a function that computes the Fibonacci sequence up to the specified number of terms. The function should take the positive integer n as input and return a list containing the first n terms of the Fibonacci sequence.

Now we are ready to start figuring the problem out!

Solution #1

From a mathematical standpoint, the Fibonacci sequence is defined recursively, therefore the most straightforward way of implementation in Python would employ recursion as well. We will start by defining a function to compute the n-th Fibonacci element.

def fibonacci_of(nth: int) -> int:
    if nth == 0:
        return 0
    if (nth == 1):
        return 1
    return fibonacci_of(nth - 1) + fibonacci_of(nth - 2)

For the zeroth element we are going to return 0, then for the first element, we are going to return 1, and then each subsequent number in the sequence is the sum of the two numbers that immediately precede it. Let's compute the first 8 terms.

print(f'0:', fibonacci_of(0))
print(f'1:', fibonacci_of(1))
print(f'2:', fibonacci_of(2))
print(f'3:', fibonacci_of(3))
print(f'4:', fibonacci_of(4))
print(f'5:', fibonacci_of(5))
print(f'6:', fibonacci_of(6))
print(f'7:', fibonacci_of(7))

Once we execute it, we get the following results.

❯ python3 main.py
0: 0
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13

Looks good so far. However, we just obtain here a single term, while the goal is to compute a sequence. Let's wrap the fibonacci_of() function into another one and name it the fibonacci(). The new function is going to return a list instead of a single term.

def fibonacci(n: int) -> list[int]:
    def fibonacci_of(nth: int) -> int:
        if nth == 0:
            return 0
        if nth == 1:
            return 1
        return fibonacci_of(nth - 1) + fibonacci_of(nth - 2)

    l = []
    for i in range(n):
      l.append(fibonacci_of(i))
    return l

We have here an additional step. We loop over the range from 0 to the n-th element, and for each element in the range, we compute the Fibonacci term. Each obtained value is appended to the list. Once the loop finishes, the list containing computed values is returned from the function. Let's add a user prompt.

def fibonacci(n: int) -> list[int]:
    def fibonacci_of(nth: int) -> int:
        if nth == 0:
            return 0
        if nth == 1:
            return 1
        return fibonacci_of(nth - 1) + fibonacci_of(nth - 2)

    l = []
    for i in range(n):
      l.append(fibonacci_of(i))
    return l

if __name__ == '__main__':
    nth_term: int = int(input(f'Provide a positive number\n'))
    sequence: list[int] = fibonacci(nth_term)
    print(f'The Fibonacci sequence up to {nth_term}th element: {sequence}')

We are ready to run the script.

❯ python3 main.py
Provide a positive number
3
The Fibonacci sequence up to 3th element: [0, 1, 1]
❯ python3 main.py
Provide a positive number
8
The Fibonacci sequence up to 8th element: [0, 1, 1, 2, 3, 5, 8, 13]

Solution #2

In the case of the previous solution, we started by defining a function that allowed us to compute a single term of the Fibonacci sequence and then we called the function multiple times to compute the sequence. That's fine, however as we already maintain the list, we have access to all previously computed terms! Why not use them?

def fibonacci(n: int) -> list[int]:
    l = []
          
    if n >= 1:
        l.append(0)
    if n >= 2:
        l.append(1)
    
    for i in range(3, n + 1):
      l.append(l[-1] + l[-2])
    return l

if __name__ == '__main__':
    nth_term: int = int(input(f'Provide a positive number\n'))
    sequence: list[int] = fibonacci(nth_term)
    print(f'The Fibonacci sequence up to {nth_term}th element: {sequence}')

We got rid of internal functions and recursive calls. Now we use an iterative approach. The last computed term is always added to the end of the list. Therefore we can take the last [-1] and the second to last [-2] terms of the list to compute the next value. The script looks now much simpler and more concise.

❯ python3 main.py
Provide a positive number
3
The Fibonacci sequence up to 3th element: [0, 1, 1]
❯ python3 main.py
Provide a positive number
8
The Fibonacci sequence up to 8th element: [0, 1, 1, 2, 3, 5, 8, 13]

When running the script, we obtain the same results. That's great news! 😂

Summary

Fibonacci used the sequence to illustrate the growth of a hypothetical population of rabbits. We provided two ways of computing the Fibonacci sequence. The first solution is based on the function that computes a single term and is called multiple times to compute the sequence. The second solution is much simpler, It doesn't involve recursion, but an iterative approach and uses already computed terms stored in the list.

References

• Fibonacci sequence - Wikipedia