Fibonacci numbers

An overview of the

The following is a brief introduction from teacher Wu Jun’s lecture 50 of General Knowledge of Mathematics.

A sequence is a tool. It looks like a string of numbers, but what’s important here is the relationship and the pattern of the numbers, not the numbers themselves. Those rules relate to how things work in our real life, and so this tool can be applied to our real world.

For example, the divergence and convergence of media retransmission, which we will talk about later, and interest, are related to geometric sequences. Take The Fibonacci number as an example, it actually reflects the changes of members in the natural reproduction of a species or the natural development of an organization. The Fibonacci sequence was originally described as follows:

There was a pair of rabbits, they gave birth to a pair of little rabbits, the front one we call generation one, the back one we call generation two. And then each of these two generations gives birth to a pair of rabbits, so you have a third generation. When the first generation of rabbits is old, they can’t give birth to little rabbits, but the second and third generations can give birth, so they give birth to the fourth generation. And then they keep multiplying. So how many pairs of NTH generation rabbits are there? The sequence is 1,1,2,3,5,8,13,21…

If we look at the growth rate of this series, it’s not as fast as 1,2,4,8,16, but it’s fast, and it’s exponential. In real life, rabbits used to breed just that fast.

In 1859, an Englishman named Thomas Austin emigrated to Australia. He liked to hunt, but finding that there were no rabbits to hunt in Australia, he sent his nephew to bring 24 rabbits from England.

The 24 rabbits arrived in Australia and were released into the wild, where, with no natural predators, they multiplied quickly. Rabbits can reproduce several generations in a year. Rabbits born at the beginning of the year become “great-grandparents” at the end of the year. A few decades later, the rabbit population had soared to 4 billion, causing a huge ecological disaster in Australia.

One might ask, why not eat rabbits? Australians did start eating rabbit meat in 1929, but not as fast as they were reproducing. The Australian government even used the army to hunt and kill, to little effect.

Finally, in 1951, a rabbit-killing virus was introduced in Australia, which wiped out more than 99 percent of the population, but the few rabbits that survived developed antiviral resistance, and the war continues to this day. What I want to say from this story is that exponential growth is really scary.

Now, let’s do a quantitative analysis of how fast the Fibonacci sequence grows. Let’s say Fn is the NTH number in the sequence, so Fn plus 1 is the NTH plus 1 number in the sequence. Let’s use Rn again, which is the ratio of Fn plus 1 to Fn, which is the ratio of the last number to the first number, and you can view these as the relative rates of growth.



OK, if you are interested, you can subscribe to this course. The rest of the course focuses on the Golden ratio, which is not our focus. Knowing this rule, we try to use different procedures to achieve the following

Function recursive

const f = function (n) {
   if(n <= 1) return 1;
   return f(n - 1) + f(n -2);
}
console.log(f(40))Copy the code

The implementation is very simple, basically using the function stack to continuously decompose the subexpression, and finally return the total value, the time complexity is exponential, and cause a lot of double calculation, so let’s run it and see how long it takes



Tail recursive call

Tail Call Overview

The Tail Call refers to the last step of a function that is to Call another function.

function f(x){
  return g(x);
}
Copy the code

In the above code, the last step of function F is to call function G, which is called a tail call.

The tail call is different from other calls because of its particular call location.

As we know, function calls form an in-memory “call record,” also known as a “call frame,” which holds information such as the location of the call and internal variables. If function B is called inside function A, then A call frame of B is formed above the call frame of A. B’s call frame will not disappear until B finishes running and returns the result to A. If C is also called from within function B, then there is a call frame for C, and so on. All call frames form a “Call stack”.

Since the last call is the last operation of the function, there is no need to retain the call frame of the outer function, because the call location, internal variables and other information will not be used, as long as the call frame of the inner function is directly replaced by the call frame of the outer function.

Code implementation

const f = function (n, prev = 1, next = 1) {
    if (n < 2) {
       return next
    }
     return f(n - 1, next, prev + next)
}
 console.log(f(40))
Copy the code

The implementation is also very simple, the basic use of tail call principle, return the function once, so let’s run it to see how long it takes



recursive

Recursive overview

Recursion is a way of describing a complex problem with several steps of repeatable operations. Recursion is a common algorithm in sequence computation. The value of a given item in a sequence is usually obtained by evaluating the preceding items.

Code implementation

function f (n = 1) {
  let i = 0, res = []
  while (i <= n) {
    if (i <= 1) {
       res[i] = 1
       i++
       continue
     }
      res[i] = res[i - 1] + res[i - 2]
      i++
  }
  return res[n]
}
 console.log(f(40))   Copy the code

The recursive way is O(n), so let’s compare which is faster in the loop and which is more expensive in the function call stack, and see the result



conclusion

We can see that function recursion is still very expensive in the real world, but using chrome’s stack debugger, we can still see that tail recursion is creating the call stack, so you can go down and try it out for yourself. More optimization ideas, welcome to discuss.