PHP实现斐波那契数列

1. 什么是斐波那契数列

斐波那契数列，也称黄金分割数列，是指这样一个数列：0、1、1、2、3、5、8、13、21、34…

特点是数列中的每一位数字都是它前面两位数字的和，即f(n) = f(n-1) + f(n-2)。

斐波那契数列的应用非常广泛，例如在金融领域可以用来进行股票价格预测、货币组合投资、期权价格等方面的计算。

2. 斐波那契数列的递归实现

斐波那契数列可以使用递归的方式实现。

function fibonacci($n) {
    if ($n == 0 || $n == 1) {
        return $n;
    } else {
        return fibonacci($n-1) + fibonacci($n-2);
    }
}

以上代码会输出斐波那契数列的第 $n$ 项。

然而，使用递归实现斐波那契数列的效率非常低，因为在计算第 $n$ 项时需要递归计算第 $n-1$ 和第 $n-2$ 项，而计算第 $n-1$ 和第 $n-2$ 项的时候还需要递归计算它们的前面两项，如此往复。每次重复计算的项数会呈指数级增长，导致当 $n$ 的值比较大时，算法的时间复杂度非常高，甚至无法计算。

3. 斐波那契数列的循环实现

为了提高斐波那契数列的计算效率，可以使用循环来实现斐波那契数列。

function fibonacci($n) {
    if ($n == 0 || $n == 1) {
        return $n;
    } else {
        $a = 0;
        $b = 1;
        for ($i = 2; $i <= $n; $i++) {
            $c = $a + $b;
            $a = $b;
            $b = $c;
        }
        return $b;
    }
}

以上代码中，$a 和 $b 分别表示计算斐波那契数列中第 $i-2$ 和第 $i-1$ 项的值。然后通过循环计算得到第 $i$ 项的值。

使用循环实现斐波那契数列的时间复杂度为 $O(n)$，相比递归实现效率更高。