Fibonacci Sequence in Python in 4 programming styles

In programming, there are often many ways to accomplish a given task. And in fact, there are different programming paradigms that allow us to create programs using different tools and abstractions. Some of them you probably already know, such as procedural programming, functional programming, etc. In this article, we'll create a Fibonacci sequence using different algorithmic design techniques.

What is the Fibonacci sequence?

The Fibonacci sequence is a simple mathematical pattern with very interesting properties that can be found in various aspects of nature. Building this sequence is very easy: start with 0 and 1, and the next elements of the sequence are just the sum of the previous two. Following these simple rules, we can find the first few numbers of the sequence:

Although knowledge of this pattern dates back thousands of years, it is usually attributed to Leonardo of Pisa (Fibonacci) who discovered it while trying to model the growth of rabbit populations under ideal conditions.

One of the properties that makes this sequence so intriguing is that the ratio between a given Fibonacci number and its predecessor asymptotically approaches the golden ratio, which is a proportion that is considered aesthetically pleasing and is present in many works of art and architecture, from the Parthenon in Athens to the Mona Lisa.

In the following section, we'll use this sequence to illustrate how different programming approaches can be used to solve the same task using different constructs.

Generating the Fibonacci sequence in Python

To calculate a specific number of the sequence, we need to know the two previous ones. That means that if we want to calculate the twentieth Fibonacci number, we would have to calculate all the previous ones first. Therefore, we have to carry out the same operation a certain number of times to find the desired value.

To achieve it, we are going to follow four different approaches that solve this problem in different ways: iteratively, recursively, functionally, and using dynamic programming. Let's see them one by one.

The iterative approach

This is probably the most common approach for solving tasks that involve repeating the same operation multiple times. The most important construct used is loops, which enable us to execute the same operation multiple times. Using this approach, we can calculate the 20th Fibonacci number as follows:

Loops are an essential part of procedural programming and are one of the first programming constructs that students learn when they start their programming journey, in part, because of their simplicity and intuitiveness.

The functional approach

Functional programming is a development paradigm where programs are created by applying and composing functions. It evolved from a formal computation system called lambda calculus.

In this paradigm, we declare our program as simple functions that we can compose hierarchically. The most basic functions, which simply produce or transform a value, are known as first-order functions. Functions that manipulate or return other functions are known as higher-order functions. Let's see this with the example of the Fibonacci sequence:

In the previous example, accumulate is a function we defined that takes two inputs: a list with the Fibonacci numbers calculated so far, and an element from a sequence. It produces an updated list with the previous Fibonacci numbers plus the next one, calculated using the two previous ones. This is a first-level function that will be manipulated by another function.

reduce, on the next line, is a higher-order function that aggregates the results of a sequence of values using a function we pass to it. In our case, the reduce function aggregates the results of the Fibonacci sequence by calling the previous function. Starting with the initial elements [0, 1], it repeats the operation with each element of the sequence range(n-1), which in this case we use as a counter and does not really intervene in the accumulate function (it appears under the name _). Finally, we return the last value from the obtained sequence, which is the requested one.

As you can see, this paradigm allows us to create our programs declaratively, based on the operations that generate the final result.

The recursive approach

Recursion is a programming tool that enables us to break down a problem into simpler versions of itself until we reach a trivial or base case. As an example, to calculate the 20th Fibonacci number, we add the 19th and 18th numbers in this sequence. Similarly, to calculate the 19th number, we add the 18th and 17th numbers, and so on. In fact, we can find the nth Fibonacci number in the following way:

In this example, fibonacci_recursive is a recursive function because it contains calls to itself. Recursion allows us to express our solution in an elegant and easy-to-understand way. In our example, the base case is when n < 2 since we have the first two numbers of the sequence (0 and 1) and don't need to calculate them. Otherwise, if n > 2, we make two recursive calls to the same function to find the two previous Fibonacci numbers and return their sum.

However, recursion also has its downsides, the most notable being inefficiency. When making recursive calls to calculate the two previous Fibonacci numbers, each of those calls in turn makes two recursive calls. This means that to calculate the n-th Fibonacci number, we must make 2^n calls to the function, repeating an enormous amount of calculations.

Dynamic programming

Dynamic programming is an algorithm design technique that, like in the previous example, recursively breaks down a problem into smaller versions of itself. However, it also stores the solutions to sub-problems to speed up calculations. In the case of calculating Fibonacci numbers, each element of the sequence depends on the previous elements. As you can see in the following diagram, many subproblems overlap and repeat the same recursive calls:

According to dynamic programming, we keep a list of the Fibonacci numbers we have already calculated to avoid recursive calls when we already know the result:

The practice of storing intermediate results to avoid unnecessary recalculation is known as memoization.

Summing up

In conclusion, the various algorithmic design paradigms explored in this article offer unique approaches to solving programming problems, each with its own properties, benefits, and drawbacks.

The choice of algorithmic design paradigm depends on the specific problem at hand and the properties we need our solution to have. By knowing a variety of design techniques, you can select the most appropriate in each situation.

In future articles we'll delve deeper into some of these techniques (and many more), so be sure to follows us.