php求斐波那契数的两种实现方式【递归与递推】

下面是详细讲解“php求斐波那契数的两种实现方式【递归与递推】”的完整攻略。

斐波那契数列

斐波那契数列，也称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……，在数学上，斐波那契数列是以递归的方式定义的。

递归求斐波那契数

递归求解斐波那契数列是一种比较简洁的方式，代码如下：

function fibonacci($n)
{
    if ($n < 2) {
        return $n;
    }
    return fibonacci($n - 1) + fibonacci($n - 2);
}

echo fibonacci(10); // 输出55

这段代码中，我们定义了一个名为fibonacci的函数，它接收一个参数$n，代表我们要求第$n$个斐波那契数。如果$n$小于2，直接返回$n$，否则递归调用自身，获取前两个斐波那契数的和，返回结果。

递推求斐波那契数

递推求解斐波那契数列也是一种有效的方式，代码如下：

function fibonacci($n)
{
    if ($n < 2) {
        return $n;
    }
    $f0 = 0;
    $f1 = 1;
    for ($i = 2; $i <= $n; $i++) {
        $fn = $f0 + $f1;
        $f0 = $f1;
        $f1 = $fn;
    }
    return $fn;
}

echo fibonacci(10); // 输出55

这段代码中，我们同样定义了一个名为fibonacci的函数，它接收一个参数$n$，代表我们要求第$n$个斐波那契数。如果$n$小于2，直接返回$n$，否则使用$f0$和$f1$来存储前两个斐波那契数，然后通过一个for循环，依次求解第2到第$n$个斐波那契数，并返回结果。

示例说明

以$n=10$为例，当我们使用递归方式时，调用了多次的函数求解，效率较低；而使用递推方式时，只需进行一次for循环，便可求解出第10个斐波那契数，效率更高。

同时，随着$n$的增大，递归方式会产生多个递归调用，导致栈溢出，而递推方式则不会存在此类问题。

因此，在实际使用中，我们应该根据不同的场景选择不同的实现方式，以达到最优的效果。