2 Ways to Calculate Fibonacci Numbers

If you are a programming beginner or know a little bit about mathematics, you have probably heard of the Fibonacci sequence at some point. According to Wikipedia, the Fibonacci sequence is a sequence in which each number is equal to the sum of the previous two numbers.

In this blog, I will go through 2 ways you can generate this sequence using Python 3.

Method 1: Recursion

In programming languages, recursion occurs whenever a function calls itself once or several times to compute an algorithm. You can read more about recursion here.

These are the steps to create this recursive function:

1. Call the function fibonacci and pass how many Fibonacci numbers (i) you want as a parameter (e.g. Input = 5, Output = [0, 1, 1, 2, 3])
2. To start the sequence, the first two Fibonacci numbers are hardcoded into the function (F[1] = 0, F[2] = 1)
3. The recursive function receives four parameters: i (Fibonacci sequence length, set to 0 by default), F[1] and F[2] (set to 0 and 1 by default respectively), and the sequence array (set to an empty list by default)
4. Inside the function, the first condition we should meet is that i is an integer and greater than 0. In the previous example, our input value will be decreasing by 1 in each iteration, and it will perform 5 iterations before reaching 0. When i is less than or equal to 0, or i is not an integer, it will return the current sequence
5. If i is not 0, the program will append the current F[1] number
6. Then, it will set F[1] equal to F[2], and F[2] equal to the sum of F[1] and F[2] (Python allows you to set multiple variables’ values simultaneously)
7. Finally, we will return the same Fibonacci function with the following parameters: i - 1, F[1], F[2], sequence

Below is the code snippet:

Method 2: For-loop

The for-loop approach shares many similarities with the previous method. Let’s check out the algorithm:

1. Call the function fibonacci and pass how many Fibonacci numbers (i) you want as a parameter (e.g. Input = 5, Output = [0, 1, 1, 2, 3])
2. Inside the function, the first condition we should meet is that i is an integer and greater than 0. If i doesn’t fulfill either condition, it will return an empty list
3. We’ll define three variables: sequence set to an empty list, F[1] and F[2] set to 0 and 1 respectively
4. Start a for-loop from 0 to i - 1 (Python’s range function starts at 0)
5. Inside the for-loop, we will append the first Fibonnacci number F[1] to the sequence
6. Just like the previous method, we’ll assign F[1] and F[2] equal to F[2] and F[1] + F[2] respectively
7. Once the loop is done, return the sequence

Here is the code: