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方面，它们在运行时是完全相同的。