PHP主|了解递归-php教程-PHP中文网

PHP 递归函数中的基例是什么？

PHP 中的递归函数是如何工作的？

PHP 中的所有问题都可以使用递归来解决吗？

如何防止 PHP 递归函数中的堆栈溢出？

什么是 PHP 中的尾递归？

PHP 中的递归与循环如何比较？

我可以使用递归来遍历 PHP 中的数组吗？

什么是 PHP 中的互递归？

如何调试 PHP 中的递归函数？

使用 PHP 中的递归有什么限制？

首页

后端开发

php教程

PHP主|了解递归

Joseph Gordon-Levitt

Feb 24, 2025 am 10:10 AM

PHP Master | Understanding Recursion

核心要点

递归是一种问题解决方法，它涉及函数直接或间接地（通过函数调用循环）调用自身。它在遍历树和列表或执行大多数 O(n log n) 排序时特别有用。
递归函数必须有一个基例或保护子句，以防止它们无限地调用自身，从而导致堆栈溢出错误。此基例是在满足特定条件时停止函数进行进一步递归调用的条件。
递归有两种类型：直接递归和间接递归。直接递归是指函数直接调用自身，而间接递归是指函数通过另一个函数间接调用自身。本文重点介绍直接递归。
虽然递归可以是一种强大的工具，但必须谨慎使用。PHP 不会优化递归函数，它们通常不如其迭代对应函数高效和快速。但是，在某些情况下，例如在文件系统中搜索或遍历不确定深度时，递归可能更有效。

在我之前的一篇文章中，我写过关于迭代器以及如何使用它们。今天，我想看看迭代的同胞兄弟：递归。不过，在我们讨论递归之前，让我们先看看这段代码：

<?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 递归函数中的基例是阻止函数无限调用自身的条件。它是任何递归函数的关键部分。如果没有基例，递归函数将无限地调用自身，导致堆栈溢出错误。在 PHP 中，基例通常使用函数开头的“if”语句定义。函数在继续进行递归调用之前检查此条件。如果满足条件，函数将返回一个值并停止调用自身。

PHP 中的递归函数是如何工作的？

PHP 中的递归函数通过在其自身函数体中调用自身，直到满足称为基例的特定条件。当调用递归函数时，它执行特定任务，然后调用自身以重复该任务。此过程持续到满足基例，此时函数停止调用自身。每次调用函数都会在调用堆栈上创建一个新层，存储函数调用的变量和返回地址。一旦满足基例，函数就开始返回，逐层解开调用堆栈。

PHP 中的所有问题都可以使用递归来解决吗？

虽然递归可以成为 PHP 中的强大工具，但并非所有问题都可以或应该使用递归来解决。递归最适合可以分解成更小、更相似的问题的问题，例如遍历文件目录或对数组进行排序。但是，如果使用不当，递归会导致高内存使用率和堆栈溢出错误。由于函数调用的开销，它通常也比迭代解决方案慢。因此，了解手头的问题并选择正确的方法非常重要。