Various Methods to Compute the Nth Fibonacci Number in PHP

The Fibonacci sequence is defined by F(1)=1, F(2)=1 and F(n)=F(n-1)+F(n-2) for n≥3. It appears in many mathematical contexts and is often used as a classic example for teaching recursion and dynamic programming.

Below are several ways to compute the Nth Fibonacci number in PHP, each with its own trade‑offs.

1. Naive Recursion

This straightforward method directly follows the mathematical definition, but it repeats many sub‑calculations and is therefore inefficient for large N.

<code>/**
 * 普通递归
 * @param int $n
 * @return int
 */
function fib($n = 1) {
    // 低位处理
    if ($n < 3) {
        return 1;
    }
    // 递归计算前两位
    return fib($n - 1) + fib($n - 2);
}
</code>

2. Recursive Optimization (Memoization)

By storing previously computed values, this version eliminates the redundant work of the naive recursion.

<code>/**
 * 递归优化
 * @param int $n
 * @param int $a
 * @param int $b
 * @return int
 */
function fib_2($n = 1, $a = 1, $b = 1) {
    if ($n > 2) {
        // 存储前一位，优化递归计算
        return fib_2($n - 1, $a + $b, $a);
    }
    return $a;
}
</code>

3. Bottom‑Up Memoization (Iterative DP)

This approach builds the sequence from the base cases upward, storing each intermediate result in an array.

<code>/**
 * 记忆化自底向上
 * @param int $n
 * @return int
 */
function fib_3($n = 1) {
    $list = [];
    for ($i = 0; $i <= $n; $i++) {
        if ($i < 2) {
            $list[] = $i;
        } else {
            $list[] = $list[$i - 1] + $list[$i - 2];
        }
    }
    // 返回最后一个数，即第N个数
    return $list[$n];
}
</code>

4. Simple Iterative Loop

Using two variables and a for‑loop, this method computes the sequence in O(N) time with O(1) extra space.

<code>/**
 * 自底向上进行迭代
 * @param int $n
 * @return int
 */
function fib_4($n = 1) {
    if ($n <= 0) return 0;
    if ($n < 3) return 1;
    $a = 0;
    $b = 1;
    // 循环计算
    for ($i = 2; $i < $n; $i++) {
        $b = $a + $b;
        $a = $b - $a;
    }
    return $b;
}
</code>

5. Closed‑Form (Binet's Formula)

By exploiting the relationship between the Fibonacci numbers and the golden ratio, this formula computes the Nth term directly.

<code>/**
 * 公式法
 * @param int $n
 * @return int
 */
function fib_5($n = 1) {
    // 黄金分割比
    $radio = (1 + sqrt(5)) / 2;
    // 斐波那契序列和黄金分割比之间的关系计算
    $num = intval(round(pow($radio, $n) / sqrt(5)));
    return $num;
}
</code>

6. Lookup Table (Hard‑Coded List)

This "cheat" method simply returns the pre‑computed value from an array of the first 30 Fibonacci numbers.

<code>/**
 * 无敌欠揍法
 * @param int $n
 * @return int
 */
function fib_6($n = 1) {
    // 列举了30个数
    $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];
}
</code>

Each method has its own advantages: the naive recursion is simple but slow, memoized recursion and DP avoid redundant work, the iterative loop is memory‑efficient, the closed‑form offers O(1) time at the cost of floating‑point precision, and the lookup table provides instant results for small N. Choose the approach that best fits your performance and readability requirements.