For more information on concepts covered in this lesson, you can check out Sorting Algorithms in Python.
Join us and get access to thousands of tutorials and a community of expert Pythonistas.
This lesson is for members only. Join us and get access to thousands of tutorials and a community of expert Pythonistas.
Hint: You can adjust the default video playback speed in your account settings.
Hint: You can set your subtitle preferences in your account settings.
Sorry! Looks like there’s an issue with video playback 🙁 This might be due to a temporary outage or because of a configuration issue with your browser. Please refer to our video player troubleshooting guide for assistance.
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.