preface

The most common way to find Fibonacci numbers in any position is to use recursion, which can yield results, but it has poor performance.

This article shares a better performance solution and invites interested developers to read it.

concept

So let’s look at what the Fibonacci sequence is, and we have a sequence where the value of position 0 is 0 and the value of position 1 is 1, and the value of position n is greater than 1 is (n-1)+(n-2).

Let’s take an example:

We want the Fibonacci number for position 5, so we want the Fibonacci number for position 5-1 and the Fibonacci number for position 5-2.

  • The Fibonacci number for position four is zerof(4-1) + f(4-2)
  • The Fibonacci number for position three is zerof(3-1) + f(3-2)
  • The Fibonacci number for position two is zerof(2-1) + f(2-2)
  • The Fibonacci number at position one is zero1
  • The Fibonacci number at position zero is zero0

As shown above, if we want to know the Fibonacci number at position 5, we need to know the Fibonacci number at position 4 and position 3, and so on to position 1 and position 0, then:

  • The Fibonacci number for position 2 is:1 plus 0 is 1
  • The Fibonacci number for position 3 is:1 plus 1 is 2
  • The Fibonacci number for position 4 is:2 plus 1 is 3
  • The Fibonacci number for position 5 is:3 plus 2 is 5

The solution

Next, let’s explain the solution to this problem in detail.

Recursive solution

Many textbooks use Fibonacci numbers as an example of recursion, so when many developers see this problem, they immediately think that it should be solved recursively.

In my other article: Understanding and Implementation of Recursion, I explained the recursive solution of Fibonacci sequence in detail. Without going into too much detail here, just draw the recursion tree for the above example, as follows:

Observing the above recursive tree, we can find that many nodes are repeated, and the number of repeated nodes will increase sharply with the increase of n, which means that the amount of computation will increase sharply with the increase of N, so its performance is very poor.

From the bottom up

The reason why the above code is slow is that there are too many repeated calculations. We can calculate f(2) from the bottom up, first from f(0) and f(1), then from f(1) and f(2) to f(3), and so on to the NTH term, whose time complexity is O(n). We call this solution bottom-up.

Let’s draw a picture to illustrate this idea:

The implementation code

Now that we have analyzed the above ideas, we can convert them into code, as follows:

export default class Fibonacci {
  private readonly index: number;
  constructor(index: number) {
    this.index = index;
  }
  
  /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** Then f(3) * 3 is calculated according to f(1) and f(2). The time complexity analysis of the NTH term * is calculated based on this: it traverses from the 0th term to the last term, so the time complexity is O(n) */
  public bottomUp(): number {
    const result: Array<number> = [0.1];
    if (this.index < 2) {
      return result[this.index];
    }

    // f(n - 1)
    let fibNMinusOne = 1;
    // f(n - 2)
    let fibNMinusTwo = 0;
    let fibN = 0;
    for (let i = 2; i <= this.index; ++i) {
      // f(n) = f(n - 1) + f(n - 2)
      fibN = fibNMinusOne + fibNMinusTwo;

      // f(n - 2) = f(n - 1)
      fibNMinusTwo = fibNMinusOne;
      // f(n - 1) = f(n)
      fibNMinusOne = fibN;
    }
    returnfibN; }}Copy the code

Let’s write a test case to execute the above code and check for correctness, as shown below. We need the value of position 100 of the Fibonacci sequence:

import Fibonacci from ".. /Fibonacci.ts";

const fibonacciTest = new Fibonacci(100);
console.log("The value of position 1000 of the Fibonacci sequence is:", fibonacciTest.bottomUp());

Copy the code

The running result is as follows:

For the complete code, go to Fibonacci. Ts

Write in the last

At this point, the article is shared.

I’m an amazing programmer, a front-end developer.

If you are interested in me, please visit my personal website for further information.

  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in nuggets. Reprint is prohibited without permission 💌