Implement Fibonacci in Python

Implementing Fibonacci in Python is one of the classical problems you need to master. It can be done in many ways, and we will cover the two main ones here.

Don’t let that stop you to proceed.

Mastering the Fibonacci problem in Python can teach you a lot.

1. Educational purposes. Fibonacci is a classic mathematical sequence that is often used as a teaching tool for introductory programming courses. By programming the Fibonacci sequence, students can learn about loops, conditional statements, and recursion.
2. Algorithm development. Fibonacci numbers are used in various algorithms, such as dynamic programming, graph algorithms, and search algorithms. By knowing how to generate Fibonacci numbers, programmers can implement these algorithms more efficiently.
3. Mathematical modeling. The Fibonacci sequence appears in various natural phenomena, such as the branching of trees and the arrangement of leaves on a stem. By programming the Fibonacci sequence, programmers can model and simulate these phenomena in their programs.
4. Cryptography. Fibonacci numbers are also used in some encryption and decryption algorithms. By programming the Fibonacci sequence, programmers can develop or implement cryptographic algorithms that rely on these numbers.

Are you ready for that?

Project Description

The Fibonacci sequence is as follows.

0 1 1 2 3 5 8 13 21 34 ... (continues)

It is generated as follows.

The next number is generated by adding the two last numbers.

0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8
8 + 13 = 21
13 + 21 = 34
21 + 34 = 55
...

Write a program that prints the Fibonacci sequence.

You will do it in two ways in this project.

Step 1 The direct way

How to solve this?

Well, the first thought is to make it in an iterative way.

def fib(n):
    if n <= 1:
        return n
    
    i = 0
    j = 1
    
    for _ in range(n):
        i, j = j, i + j
        
    return i

You try to follow how the sequence is calculated and this can be done but seems easy to get lost in the code.

To generate the sequence you can run this code.

for i in range(10):
    print(fib(i))

Step 2 The simple way (recursive)

The first time you see recursion, it might not be easy to understand.

But after inspecting the following code, you might find it easier to write and follow.

def fib(n):
    if n <= 1:
        return n

    return fib(n - 1) + fib(n - 2)

This actually generates the same sequence.

The code is actually writing the exact formula for generating it.

You can get the sequence as follows.

for i in range(10):
    print(fib(i))

Want more Python projects?

This is part of 19 Python Projects and you can build the classical guess number game and sharpen 6 essential skills.