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.
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.
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.
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.
Become a Member to join the conversation.