PHP中递归计算斐波那契数列为何耗时更长？

测试代码 #

// 递归计算指定索引的斐波那契值
function fibonacciRecursiveAtIndex($num){
    if($num == 0){
        return 0;
    } else if ($num == 1){
        return 1;
    } else {
        return fibonacciRecursiveAtIndex($num-1) + fibonacciRecursiveAtIndex($num-2);
    }
}

// 非递归计算指定索引的斐波那契值
function fibonacciAtIndex($num){
    $fibonacciArray = [0, 1];

    for($i = 2; $i < $num + 1; $i++){
        array_push($fibonacciArray, $fibonacciArray[$i - 1] + $fibonacciArray[$i - 2]);
    }
    
    return $fibonacciArray[$num];
}

// 索引大于15时递归性能会明显下降
$indexToCalculate = 40;

// 调用递归函数并输出耗时
$timeStart = microtime(true);
$valueAtIndex = fibonacciRecursiveAtIndex($indexToCalculate);
$timeEnd = microtime(true);
echo "Recursive(" . $indexToCalculate . ") = " . $valueAtIndex . " -- calculated in " . round(($timeEnd - $timeStart),7) . " s";

echo "<br><br>";

// 调用非递归函数并输出耗时
// 大索引（>15）下耗时比递归快几个数量级
$timeStart = microtime(true);
$valueAtIndex = fibonacciAtIndex($indexToCalculate);
$timeEnd = microtime(true);

echo "Fibonacci(" . $indexToCalculate . ") = " . $valueAtIndex . " -- calculated in " . round(($timeEnd - $timeStart),7) . " s";

问题 #

运行这段代码计算索引40处的斐波那契值时，递归方法耗时约4秒，而数组方法计算索引40和索引4的耗时几乎相同（均为微秒级）。请问该现象背后的原理是什么，以及该原理在此场景下如何体现？

原理解析 #

1. 递归实现的性能瓶颈：指数级复杂度与重复计算 #

标准无记忆化的递归斐波那契实现，时间复杂度是O(2ⁿ)（n为目标索引）：

• 计算fib(40)时，需要先算fib(39)和fib(38)；算fib(39)又要重复计算fib(38)和fib(37)——这里fib(38)就被重复计算了一次。
• 越往底层，重复计算的次数会爆炸式增长：比如fib(2)会被计算数百万次，每次递归调用还要额外消耗栈空间、函数调用的系统开销，这些累积起来直接导致耗时飙升到秒级。

2. 迭代（数组）实现的性能优势：线性复杂度与无重复计算 #

基于数组的迭代实现，时间复杂度是O(n)，空间复杂度为O(n)（还可以优化到O(1)）：

• 它从已知的fib(0)和fib(1)出发，一步步向上推导每个索引的值，每个值只计算一次，计算结果直接存在数组中供后续步骤复用。
• 就算索引从4涨到40，也只是多执行36次简单的加法和数组插入操作，这些操作本身都是微秒级的，所以整体耗时几乎没有明显变化。

本质上，递归是“拆分问题时不断重复解决同一个子问题”，而迭代是“从基础结果出发，逐步构建最终结果”，前者的无效劳动随索引增长呈指数级上升，后者则始终保持高效的线性增长。

内容的提问来源于stack exchange，提问作者N.MORR