According to Donald Ervin Knuth’s The Art of Computer Programming, in 1150 The Indian mathematicians Gopala and Jin Yuk were studying The number of possible ways in which boxes could contain objects exactly 1 and 2 in length and width, So let’s describe this sequence. The first person to study this sequence in the West was Leonardo of Pisa (Leonardo Fibonacci), who used it to describe the number of rabbits growing:

  • At the beginning of the first month there was a pair of newborn rabbits
  • After the second month (the beginning of the third month) they can reproduce
  • Each fertile pair of rabbits produces a new pair each month
  • Rabbits never die

So let’s say we have rabbits in n months total a pairs, n plus 1 months total B pairs. In n+2 there must be a total of A + B pairs: because in n+2, the B pairs of the previous month (n+1) can survive until n+2 (the new rabbits are not fertile in that month). And the logarithm of newly born rabbits is equal to all of the a pairs that have existed in n months

The Fibonacci sequence starts with 0 and 1, and the Fibonacci coefficients are the sum of the previous two numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…

If we use mathematical language to describe it, it would look like this:? F_0 = 0? ? F_1 = 1? ? Fn = F(n-1) + F_(n-2)?

Recursive solution

If you’ve learned how to program, your first instinct is to use recursion:

def fib(n):
    assert n >= 0.'input invalid'
    return n if n<=1 else fib(n- 1) + fib(n2 -)Copy the code
function fib(n) {
    return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}Copy the code

The nice thing about recursion is that the code is clean and neat, and it doesn’t feel like a mess

The process of this recursive solution method can be simplified into a binary tree as shown in the figure below:

Fibonacci binary tree


Here’s how long it took me to recursively solve Fibonacci number 41 in different languages:

fibonacci_speed_compare

Ps: The system time command is directly used to calculate the running time and other information

Why not recommend recursive solution

Because he thinks programmers don’t need recursion at all, he refuses to add tail-recursion optimizations to Python, and even raises RuntimeError when the recursion depth exceeds 1000: Maximum recursion depth exceeded For details, see Tail recursion Elimination

I don’t think recursion is fundamental to programming. Recursion is something that computer scientists, especially those who love Scheme (a branch of Lisp) and use ‘cons’ to teach heads, tails and recursion. But for Guido, recursion is just a theoretical tool for basic mathematical research (such as fractal geometry), not an everyday programming tool.

The Python philosophy is “There should be one– and preferably only one– obvious way to do it”. This philosophy is embodied in Turtle’s insistence that Python be optimized without tail recursion. This design philosophy not only reduces the cognitive burden and choice cost of development, but also helps improve development efficiency. At the same time, this feature keeps Python code from being written by different people, which is useful for teamwork.

The recursion turns into a non-recursive solution

Therefore, our Fibonacci sequence cannot be solved directly by recursion. The more common idea is to change recursion to recursion, initialize the first two Fibonacci terms into an array, and then calculate each subsequent term in a loop according to f(n) = F (n-1) + f(n-2). The time complexity of this algorithm is O(n). I tested it on my computer, and the code below solved item 41 in 0.02 seconds.

def fast_fib(n):
    f = [0.1]
    for i in range(2, n+1):
        f.append(f[i- 1] + f[i2 -])
    return f[n]Copy the code

Compare recursion and recursion: both use the divide-and-conquer idea – break the target problem into several smaller problems and use the solution of the smaller problem to get the solution of the target problem. The difference between the two is actually the difference between ordinary divide-and-conquer algorithm and dynamic programming.

Is that the end of the question

There’s a more subtle way to do it (except by using the general term formula)

We first write the two adjacent terms of the Fibonacci sequence, F(n) and F(n-1), as a 2×1 matrix and then transform it:

Further deduction can be obtained:

If you do it with a matrix, it’s order log n in time, order one in space.

The derivation of the general term formula of the Fibonacci sequence is also a very interesting topic, which can be derived by using the generating function. I won’t expand it here

Fibonacci sequence: Code performance optimization