1

この質問によって: PHP は末尾再帰を最適化しますか?

php は末尾再帰を最適化しません

しかし、自分のマシンで試してみると、(php 5.3.10)

フィボナッチの 2 つのプログラム: 1 つは通常の再帰、もう 1 つは末尾再帰です。

使用される時間プログラムは大きく異なります。

そして、私はそれについて混乱しています.phpが最適化しない場合、末尾再帰が通常の再帰よりも速い理由を誰が教えてくれますか?</p>

fibonacci.php:

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

fibonacci2.php:

<?php
function fibonacci2($n, $acc1, $acc2) {
    if ($n == 0) {
        return $acc1;
    }   
    return fibonacci2($n-1, $acc2, $acc1 + $acc2);
}

var_dump(fibonacci2(30, 0, 1));
4

1 に答える 1

2

2 番目のスクリプトは、末尾再帰を使用するためではなく、再帰の合計回数が少ないため高速です。

(最初のスクリプトは、各レベルで自分自身を 2 回呼び出します。2 番目のスクリプトは、各レベルで自分自身を 1 回だけ呼び出します。そのため、2 番目のスクリプトは、最初のスクリプトよりもはるかに少ない作業で終わります。)

于 2012-07-10T01:33:54.677 に答える