PHP中的遞歸遞歸比正常遞歸慢嗎？

Question

我在PHP中做了2個階乘函數的版本用於基準測試，一個使用正常遞歸，另一個使用尾遞歸。後者應該更快，但結果顯示不然。我在這裏錯過了什麼嗎？

我的代碼如下，包括基準測試：

<?php 
benchmark(); 

function benchmark() 
{ 
    $n = 10; 
    $multiplier = 10000; 
    $functions = array('factorial_recursive', 'factorial_tailRecursive'); 

    foreach ($functions as $function) { 
     $start = microtime(true); 
     echo $function . '<br>'; 
     echo $function($n) . '<br>'; 
     echo ($multiplier * (microtime(true) - $start)) . '<br><br>'; 
    } 
} 

function factorial_recursive($n) 
{ 
    if ($n == 1) { 
     return $n; 
    } 

    return $n * factorial_recursive($n - 1); 
} 

function factorial_tailRecursive($n, $result = 1) 
{ 
    if ($n == 1) { 
     return $result; 
    } 

    return factorial_tailRecursive($n - 1, $result * $n); 
} 

打印輸出：

factorial_recursive 
3628800 
2.4199485778809 

factorial_tailRecursive 
3628800 
2.5296211242676 

任何瞭解讚賞 - 感謝！

Answer 1

爲了在命令行上運行（將br轉換爲換行符，調整了輸出格式），我把你的代碼修改了一下。另外，我改變了它，使基準運行25次迭代，而不是隻有一個：

<?php 
foreach (range(1, 25) as $iteration) { 
    benchmark($iteration); 
} 

function benchmark($iteration) 
{ 
    $n = 10; 
    $multiplier = 10000; 
    $functions = array('factorial_recursive', 'factorial_tailRecursive'); 

    echo "\nIteration {$iteration}:\n"; 
    foreach ($functions as $function) { 
     $start = microtime(true); 
     echo $function . "\n"; 
     echo $function($n) . "\n"; 
     echo ($multiplier * (microtime(true) - $start)) . "\n\n"; 
    } 
} 

function factorial_recursive($n) 
{ 
    if ($n == 1) { 
     return $n; 
    } 

    return $n * factorial_recursive($n - 1); 
} 

function factorial_tailRecursive($n, $result = 1) 
{ 
    if ($n == 1) { 
     return $result; 
    } 

    return factorial_tailRecursive($n - 1, $result * $n); 
} 

這裏是我的PHP CLI版本：

$ php --version 
PHP 5.3.10-1ubuntu3.4 with Suhosin-Patch (cli) (built: Sep 12 2012 19:00:43) 
Copyright (c) 1997-2012 The PHP Group 
Zend Engine v2.3.0, Copyright (c) 1998-2012 Zend Technologies 
    with Xdebug v2.1.0, Copyright (c) 2002-2010, by Derick Rethans 

這裏是我的25次迭代的結果：

$ php ./benchmark.php 

Iteration 1: 
factorial_recursive 
3628800 
0.46014785766602 

factorial_tailRecursive 
3628800 
0.33855438232422 


Iteration 2: 
factorial_recursive 
3628800 
0.26941299438477 

factorial_tailRecursive 
3628800 
0.26941299438477 


Iteration 3: 
factorial_recursive 
3628800 
0.27179718017578 

factorial_tailRecursive 
3628800 
0.2598762512207 


Iteration 4: 
factorial_recursive 
3628800 
0.26941299438477 

factorial_tailRecursive 
3628800 
0.2598762512207 


Iteration 5: 
factorial_recursive 
3628800 
0.28848648071289 

factorial_tailRecursive 
3628800 
0.28848648071289 


Iteration 6: 
factorial_recursive 
3628800 
0.27894973754883 

factorial_tailRecursive 
3628800 
0.27894973754883 


Iteration 7: 
factorial_recursive 
3628800 
0.29087066650391 

factorial_tailRecursive 
3628800 
0.2598762512207 


Iteration 8: 
factorial_recursive 
3628800 
0.25033950805664 

factorial_tailRecursive 
3628800 
0.25033950805664 


Iteration 9: 
factorial_recursive 
3628800 
0.25033950805664 

factorial_tailRecursive 
3628800 
0.2598762512207 


Iteration 10: 
factorial_recursive 
3628800 
0.25033950805664 

factorial_tailRecursive 
3628800 
0.24795532226562 


Iteration 11: 
factorial_recursive 
3628800 
0.25033950805664 

factorial_tailRecursive 
3628800 
0.27894973754883 


Iteration 12: 
factorial_recursive 
3628800 
0.27894973754883 

factorial_tailRecursive 
3628800 
0.27894973754883 


Iteration 13: 
factorial_recursive 
3628800 
0.2598762512207 

factorial_tailRecursive 
3628800 
0.25033950805664 


Iteration 14: 
factorial_recursive 
3628800 
0.25033950805664 

factorial_tailRecursive 
3628800 
0.27179718017578 


Iteration 15: 
factorial_recursive 
3628800 
0.25033950805664 

factorial_tailRecursive 
3628800 
0.24795532226562 


Iteration 16: 
factorial_recursive 
3628800 
0.24080276489258 

factorial_tailRecursive 
3628800 
0.25033950805664 


Iteration 17: 
factorial_recursive 
3628800 
0.27179718017578 

factorial_tailRecursive 
3628800 
0.25033950805664 


Iteration 18: 
factorial_recursive 
3628800 
0.24080276489258 

factorial_tailRecursive 
3628800 
0.25033950805664 


Iteration 19: 
factorial_recursive 
3628800 
0.25033950805664 

factorial_tailRecursive 
3628800 
0.25033950805664 


Iteration 20: 
factorial_recursive 
3628800 
0.25033950805664 

factorial_tailRecursive 
3628800 
0.2598762512207 


Iteration 21: 
factorial_recursive 
3628800 
0.24795532226562 

factorial_tailRecursive 
3628800 
0.23841857910156 


Iteration 22: 
factorial_recursive 
3628800 
0.30040740966797 

factorial_tailRecursive 
3628800 
0.29087066650391 


Iteration 23: 
factorial_recursive 
3628800 
0.30994415283203 

factorial_tailRecursive 
3628800 
0.26226043701172 


Iteration 24: 
factorial_recursive 
3628800 
0.29087066650391 

factorial_tailRecursive 
3628800 
0.32186508178711 


Iteration 25: 
factorial_recursive 
3628800 
0.27894973754883 

factorial_tailRecursive 
3628800 
0.30040740966797 

看着這些結果，我不得不說這個差別可以忽略不計，太接近了。至少在Big-O方面，它們在運行時是完全相同的。