Fibonacci sequence
In a previous lesson I explained how to use recursion to calculate the Fibonacci sequence:
The result obtained is as follows:
What is Fibonacci?
In the Middle Ages, Fibonacci discovered an interesting mathematical problem, if we start with a pair of bunnies, it will take a month for the pair to grow up, after which they will breed to produce another pair of bunnies. The pair of bunnies will then spend a month growing up, and the larger rabbit will continue to breed the bunnies as they grow older. Fibonacci assumes that rabbits don't die, so there is a Fibonacci model:
The first and second numbers in the Fibonacci sequence are 1, and the third number is equal to the sum of the first and second numbers. The fourth number is equal to the sum of the second and third numbers. And so on, each term is equal to the sum of the previous two.
recursive method
Obviously this problem can be solved recursively: if we want to know the value of the fourth term of the Fibonacci sequence, we need to know the value of the second and third terms of the Fibonacci sequence, where the second term is 1 , if we want to know the value of the third term of the Fibonacci sequence, we need to know the value of the first and second terms of the Fibonacci sequence, both of which are 1. So the recursive program is written:
I can add an output to the function so we can see exactly what terms are computed by the function:
We can call fib(10) to see exactly how much this function computes:
We can call fib(15) to see exactly how much this function computes:
The complexity of computing the Fibonacci sequence using recursion increases exponentially with N! This is something that computers can't afford! If we want to calculate the 100th term of the Fibonacci sequence, then I am afraid it will take several days and dozens of gigabytes of memory.
Python provides us with a way to quickly make recursion easy: lru_cache, which can memorize results that have already been generated, so that Python doesn't need to recompute what has already been computed. Especially useful when generating Fibonacci sequences:
We still run fib(15), and the output is very different from before:
Because of the memory with lru_cache, the program only calculates 15 times, and the result of each time is saved in a python array.
We can even calculate the 100th term of the Fibonacci sequence like this, which must be an astronomical number:
The calculation results are as follows:
We can also try subsequent items, such as the 1000th item, but python has a recursion depth limit, and an error will be reported if this limit is exceeded:
Use the following statement to set the recursion limit to 10000 so that calculating the 1000th term of the Fibonacci sequence will not exceed the python limit.
The complete recursive program looks like this:
The result is a fairly large number:
And you will find that the calculation speed is extremely fast after using lru_cache, and it basically does not take time.
loop method
There are three ways to calculate the Fibonacci sequence in python. The circular method ranks in the middle. Whether it is the difficulty of this method or the amount of calculation, the circular method performs well.
The above function can calculate the result of the first ten terms of the Fibonacci sequence:
In each calculation, b is equal to the sum of the two items, and a is equal to b, so it is like pulling a zipper(Climb up step by step.) to calculate the Fibonacci sequence.
Mathematical method
In the previous two methods, if we need to calculate the N-th term of the Fibonacci sequence, we need to calculate all the previous terms, which will take a long time. Mathematical methods are not required these at all. First, the general term formula of the Fibonacci sequence is obtained through mathematical method, and then any term of the Fibonacci sequence can be obtained by only one calculation:
Got the following result:
The mathematical method is very fast, but it should be noted that exponentiation is not a basic operation, and exponentiation takes a lot of CPU time, so this method is not as good as expected.
Summarize
Of the above methods, the slowest is the recursive method, which uses exponential time complexity. If you want to calculate the 100th item, modern computers cannot give the result in 1 minute. That is to say, this method fails.
The recursive method which uses lru_cache and looping methods are easy to think of and easy to program and not difficult for computer to finish running in time, which are highly recommended here.
Mathematical methods are generally the fastest, but also the hardest to come up with, so are not highly recommended here. In general, the built-in functions of python are optimized using mathematical methods, which is why it is difficult for the algorithms you write to outperform the functions that come with python.
Statistics
Start time of this page: January 13, 2022
Completion time of this page: January 13, 2022
Last updated
