For more information on concepts covered in this lesson, you can check out Sorting Algorithms in Python.

# Implementing a Minimal Recursive Algorithm

**00:00**
A Minimal Recursive Algorithm in Python. The most common and minimal algorithm to generate the Fibonacci sequence requires you to code a recursive function that calls itself as many times as needed until it computes the desired Fibonacci number.

**00:41**
Inside `fibonacci_of()`

, you first check the base case and return an appropriate value if it is one. If the value is not a base case, you would instead return the sum of the values that results from calling the function with the two preceding values of `n`

. The list comprehension at the end of the example generates a Fibonacci sequence with the first fifteen numbers.

**01:05**
This function quickly falls into the repetition issue you saw in the previous section. The computation gets more and more expensive as `n`

gets bigger.

**01:14**
The required time grows exponentially because the function calculates many identical sub-problems over and over again. Note that you shouldn’t try to use this function at home with a number greater than fifty. Depending on your hardware, you might be waiting for a long time before seeing the result, indeed if you make it to the end at all. To calculate *F(5)*, `fibonacci_of()`

has to call itself fifteen times.

**01:41**
To calculate *F(N)*, the maximum depth of the call tree is *N*, and since each function call produces two additional function calls, the time complexity of this recursive function is *O(2ᴺ)*.

**01:55**
For more on time complexity, check out this Real Python course.

**02:02**
Most of those calls are redundant because you’ve already calculated their results. *F(3)* appears twice, and *F(2)* appears three times. *F(1)* and *F(0)* are base cases, so it’s fine to call them multiple times.

**02:18**
As the size of the calculation grows, it’s worthwhile to avoid this repetition, and this is what’s covered in the next section of the course.

Become a Member to join the conversation.