php - 尾递归比 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 方面是这样。