核心要点
在我之前的一篇文章中，我写过关于迭代器以及如何使用它们。今天，我想看看迭代的同胞兄弟：递归。不过，在我们讨论递归之前，让我们先看看这段代码：
<?php
function factorial($number) {
if ($number < 0) {
throw new InvalidArgumentException('Number cannot be less than zero');
}
$factorial = 1;
while ($number > 0) {
$factorial *= $number;
$number--;
}
return $factorial;
}阶乘是一个数乘以小于该数的所有正整数的结果，上面的函数使用简单的循环计算任何给定数字的阶乘。现在让我们这样重写这个例子：
<?php
function factorial_recursive($number) {
if ($number < 0) {
throw new InvalidArgumentException('Number cannot be less than zero');
}
if ($number == 0) {
return 1;
}
return $number * factorial_recursive($number - 1);
}当我们调用这两个函数时，我们得到相同的结果，但是请注意，第二个函数通过调用自身来计算阶乘。这被称为递归。
什么是递归？
递归函数是指直接或通过函数调用循环调用自身的函数。递归也可以指一种问题解决方法，它首先解决问题的较小版本，然后使用该结果加上一些其他计算来形成对原始问题的答案。通常，在解决较小版本的过程中，该方法将解决更小版本的难题，依此类推，直到达到易于解决的“基例”。要编写递归函数，您需要为其提供某种返回方法，否则它将永远（或直到调用堆栈爆裂、脚本超时或内存耗尽）不断调用自身。这被称为保护子句或基例。递归函数的最简单形式如下：
<?php
function my_recursive_func(args) {
if (simplest case) {
// 停止函数无限运行的基例/保护子句
return simple value;
}
else {
// 使用更简单的参数再次调用函数
my_recursive_func(argsSimplified);
}
}递归类型
当函数直接调用自身时，称为直接递归。函数在一个函数调用循环中最终调用自身称为间接递归。请查看下面间接递归的示例：
<?php
function A($num) {
$num -= 1;
if($num > 0) {
echo "A is Calling B($num)\n";
$num = B($num);
}
return $num;
}
function B($num) {
$num -= 2;
if($num > 0) {
echo "B is Calling A($num)\n";
$num = A($num);
}
return $num;
}
$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);<code>Calling A(4) A is Calling B(3) B is Calling A(1) Result: 0</code>
上面的例子实际上是无用的代码，只是为了向您展示函数如何通过另一个函数间接调用自身。调用 A(n>4) 或 B(n>4) 会导致从另一个函数调用调用的函数。重要的是要知道函数可以像这样间接调用自身，但在本文中，我们只处理直接递归。
一个实际的例子
为了向您展示递归的强大功能，我们将编写一个在数组中搜索键并返回结果的函数。
<?php
function factorial($number) {
if ($number < 0) {
throw new InvalidArgumentException('Number cannot be less than zero');
}
$factorial = 1;
while ($number > 0) {
$factorial *= $number;
$number--;
}
return $factorial;
}<?php
function factorial_recursive($number) {
if ($number < 0) {
throw new InvalidArgumentException('Number cannot be less than zero');
}
if ($number == 0) {
return 1;
}
return $number * factorial_recursive($number - 1);
}一切都很顺利，但是请注意，我们只迭代到数组的第二层，因此在第三层中搜索“Fibonacci”失败了。如果我们要搜索不确定深度的数组，这将不够用。我们可以将搜索重写为递归函数：
<?php
function my_recursive_func(args) {
if (simplest case) {
// 停止函数无限运行的基例/保护子句
return simple value;
}
else {
// 使用更简单的参数再次调用函数
my_recursive_func(argsSimplified);
}
}使用递归函数，我们可以搜索几层深的数组，因为我们没有硬编码函数的深度。它只是不断运行，直到遍历数组中的所有值。
头递归和尾递归
在我们迄今为止的所有示例中，我们一直在使用所谓的头递归。当函数调用自身时，它会在返回自身值之前等待来自调用的结果。可以编写函数，使其不操作返回值，而是将所有必需的值作为参数传递。这称为尾调用（或尾递归）。此方法通常是首选，因为语言的运行时有时可以优化调用，因此不会有爆破调用堆栈的危险，但 PHP 不会这样做。以下是我们的阶乘示例，修改为进行尾调用。请注意，返回递归调用的结果，而不是进一步操作它。
<?php
function A($num) {
$num -= 1;
if($num > 0) {
echo "A is Calling B($num)\n";
$num = B($num);
}
return $num;
}
function B($num) {
$num -= 2;
if($num > 0) {
echo "B is Calling A($num)\n";
$num = A($num);
}
return $num;
}
$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);一般建议
任何可以用迭代方式编写的代码也可以用递归方式编写。但是，这并不总是容易做到（甚至明智）。递归在遍历树和列表或执行大多数 O(n log n) 排序时非常出色。当您需要划分重复性问题时，递归比迭代方法更适合，例如在文件系统中搜索，并且您还需要进入任何子目录进行搜索。在遍历不确定深度的地方，递归效果很好。请记住，PHP 不会优化递归函数，即使您编写它们以进行尾调用，递归函数通常也比其迭代对应函数效率低且速度慢，尽管它们有时可以更好地完成工作，如上面的代码示例所示。递归通常是函数式编程中迭代的首选替代方法，因此大多数函数式语言都会优化递归函数。如果您使用的是 XDebug，请务必检查您系统的配置。默认情况下，您将限制 100 次递归调用，如果您超过此限制，您的脚本将抛出“已达到最大嵌套限制”错误。如果您需要更改此设置，可以更新 debug.max_nesting_level 配置值。最后，最好阅读堆栈堆和递归导致堆栈溢出的解释，以了解在递归期间调用堆栈会发生什么情况。
结论
在本文中，我向您广泛介绍了递归及其与迭代的比较。我还向您展示了如何编写递归函数、何时编写它们以及原因。我还试图警告您使用递归时可能会遇到的一些陷阱。递归是这样的，即使许多经验丰富的程序员也可能多年不用它，而许多其他人甚至从未听说过它，这令人遗憾，因为它是一个真正强大的概念。我希望通过这篇文章，我可以为您提供足够的知识，让您开始编写自己的递归函数。但请记住，就像使用火一样，您必须始终小心谨慎地使用此工具。
图片来自 Alexandre Duret-Lutz 通过 Flickr
关于理解 PHP 中递归的常见问题解答 (FAQ)
PHP 递归函数中的基例是阻止函数无限调用自身的条件。它是任何递归函数的关键部分。如果没有基例，递归函数将无限地调用自身，导致堆栈溢出错误。在 PHP 中，基例通常使用函数开头的“if”语句定义。函数在继续进行递归调用之前检查此条件。如果满足条件，函数将返回一个值并停止调用自身。
PHP 中的递归函数通过在其自身函数体中调用自身，直到满足称为基例的特定条件。当调用递归函数时，它执行特定任务，然后调用自身以重复该任务。此过程持续到满足基例，此时函数停止调用自身。每次调用函数都会在调用堆栈上创建一个新层，存储函数调用的变量和返回地址。一旦满足基例，函数就开始返回，逐层解开调用堆栈。
虽然递归可以成为 PHP 中的强大工具，但并非所有问题都可以或应该使用递归来解决。递归最适合可以分解成更小、更相似的问题的问题，例如遍历文件目录或对数组进行排序。但是，如果使用不当，递归会导致高内存使用率和堆栈溢出错误。由于函数调用的开销，它通常也比迭代解决方案慢。因此，了解手头的问题并选择正确的方法非常重要。
可以通过仔细定义函数最终将达到的基例来防止递归函数中的堆栈溢出。基例是一个条件，当满足此条件时，函数将停止进行进一步的递归调用。如果没有基例，函数将无限地调用自身，导致堆栈溢出。同样重要的是要确保每次递归调用都使函数更接近基例，以避免无限递归。
尾递归是一种特殊的递归，其中递归调用是函数中的最后一个操作。这意味着无需跟踪之前的函数调用，允许编译器或解释器优化递归并降低堆栈溢出的风险。但是，PHP 本身并不支持尾递归优化。因此，虽然您可以在 PHP 中编写尾递归函数，但它们不会被优化，并且仍然会为每次递归调用消耗堆栈空间。
递归和循环都可以用于在 PHP 中重复一组指令。但是，它们的工作方式不同，并且具有不同的优缺点。递归是解决可以分解成更小、更相似问题的复杂问题的强大工具。它对于遍历树或图之类的任务特别有用。另一方面，循环通常更适合简单的重复性任务。它们比递归使用更少的内存，并且不太可能导致堆栈溢出。
是的，递归可以成为遍历 PHP 中数组（尤其是多维数组）的非常有效的方法。可以使用递归函数迭代数组中的每个元素，如果元素本身也是数组，则函数可以调用自身来迭代该数组。此过程持续到访问所有元素为止。但是，请记住，递归可能比迭代解决方案慢，并且会使用更多内存，尤其是在大型数组的情况下。
互递归是指两个或多个函数以循环方式相互调用。在 PHP 中，这意味着函数 A 调用函数 B，而函数 B 调用函数 A。这可以成为解决某些类型问题的强大工具，但它也可能比简单的递归更难理解和调试。与任何递归函数一样，重要的是定义一个基例以防止无限递归。
由于函数多次调用自身，因此调试 PHP 中的递归函数可能具有挑战性。但是，您可以使用多种策略。一种方法是使用打印语句或调试器来跟踪函数调用并查看每个步骤中变量的状态。另一种方法是绘制递归树以可视化函数调用。同样重要的是要仔细检查基例和递归情况以确保它们是正确的。
虽然递归可以成为 PHP 中的强大工具，但它确实有一些限制。主要限制之一是如果递归太深，则存在堆栈溢出的风险。这是因为每次递归调用都会在调用堆栈中添加一个新层，并且堆栈大小是有限的。由于函数调用的开销，递归也可能比迭代解决方案慢，并且会使用更多内存。此外，递归函数可能比迭代解决方案更难理解和调试。
以上是PHP主|了解递归的详细内容。更多信息请关注PHP中文网其他相关文章！
