foreword

Some time ago, I encountered a conventional recursive method for optimizing the calculation of the Fibonacci sequence, but I didn't think of a good method in time, so I searched for relevant information later, and summarized a variety of calculation solutions, so I shared it with everyone. Exchange learning.

What are Fibonacci numbers

The Fibonacci sequence, also known as the golden section sequence, was introduced by the mathematician Leonardoda Fibonacci with the example of rabbit breeding, so it is also known as the "rabbit sequence". is such a sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, ... In mathematics, the Fibonacci sequence is defined recursively as follows: F(1)= 1, F(2)=1, F(n)=F(n - 1)+F(n - 2) (n ≥ 3, n ∈ N*).

Knowing the Fibonacci number, then we will use a variety of different methods to calculate and obtain the N th Fibonacci number.

ordinary recursion

This method is the most conventional, and can be calculated recursively directly according to the definition F(n)=F(n - 1)+F(n - 2), but the performance is the lowest.

/**
 * ordinary recursion
 * @param int $n
 * @return int
 */
function fib($n = 1)
{
    // low-order processing
    if ($n < 3) {
        return 1;
    }
    // Recursively calculate the first two digits
    return fib($n - 1) + fib($n - 2);
}

recursive optimization

As can be seen from the above recursive method, a lot of repeated calculations are performed, and the performance is extremely poor. If N is larger, the number of calculations is too terrible. Then, since the performance is affected by repeated calculations, the optimization starts from reducing repeated calculations. , that is, to store the previously calculated data, which avoids too many repeated calculations and optimizes the recursive algorithm.

/**
 * recursive optimization
 * @param int $n
 * @param int $a
 * @param int $b
 * @return int
 */
function fib_2($n = 1, $a = 1, $b = 1)
{
    if ($n > 2) {
        // Store the previous bit, optimize recursive calculation
        return fib_2($n - 1, $a + $b, $a);
    }
    return $a;
}

memoization bottom-up

A subproblem of computing Fibonacci numbers by iteratively bottom-up and storing the computed values, computes over the computed values. Use for loops to reduce the repetitive calculation problem caused by recursion.

/**
 * memoization bottom-up
 * @param int $n
 * @return int
 */
function fib_3($n = 1)
{
    $list = [];
    for ($i = 0; $i <= $n; $i++) {
        // From low to high digits, store them in the array in turn
        if ($i < 2) {
            $list[] = $i;
        } else {
            $list[] = $list[$i - 1] + $list[$i - 2];
        }
    }
    // Returns the last number, which is the N th number
    return $list[$n];
}

Iterate from the bottom up

Lowest bit initialization assignment, use for Iteratively calculate from low to high to get the first N number.
/**
 * Iterate from the bottom up
 * @param int $n
 * @return int
 */
function fib_4($n = 1)
{
    // low-order processing
    if ($n <= 0) {
        return 0;
    }
    if ($n < 3) {
        return 1;
    }
    $a = 0;
    $b = 1;
    // loop calculation
    for ($i = 2; $i < $n; $i++) {
        $b = $a + $b;
        $a = $b - $a;
    }
    return $b;
}

formula method

Calculate the N th Fibonacci number using the golden ratio by understanding the relationship between the Fibonacci sequence and the golden ratio.

/**
 * formula method
 * @param int $n
 * @return int
 */
function fib_5($n = 1)
{
    // golden ratio
    $radio = (1 + sqrt(5)) / 2;
    // Calculation of the relationship between the Fibonacci sequence and the golden ratio
    $num = intval(round(pow($radio, $n) / sqrt(5)));
    return $num;
}

Invincible Punishment

I won't say more about this method, everyone knows it, but don't try it lightly...

/**
 * Invincible Punishment
 * @param int $n
 * @return int
 */
function fib_6($n = 1)
{
    // 30 numbers listed
    $list = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269];
    return $list[$n];
}