避免函数调用：在 PHP 中使用非递归技巧

云游道人 2024-11-25 612 阅读 0评论

在编程中，递归常被视为计算阶乘、斐波那契数列以及遍历树等任务的优选方法。然而，递归并非没有局限性。如果递归深度过深，可能会导致堆栈溢出错误。此外，函数调用在内存和性能方面也可能比较昂贵。在某些情况下，您可能需要避免使用递归，而选择在循环中完成逻辑操作，以提升效率。

本文将探讨在 PHP 中使用堆栈、循环和 goto 语句来模拟递归行为，从而在不调用函数的情况下解决常见的递归问题。

请注意，这并非对递归函数的褒贬之词，而仅仅是一次知识分享。您选择递归还是迭代，通常取决于具体问题。了解这两种技术可以扩展您的工具箱。

我们将介绍三种方法来实现模拟递归的行为：

1. 使用堆栈进行阶乘计算

阶乘是指一个正整数和它所有小于它的正整数的乘积。比如，5 的阶乘（记作 5!）等于 5 x 4 x 3 x 2 x 1 = 120。

为了模拟递归计算阶乘，我们可以使用堆栈。堆栈是一种抽象数据类型，其元素按照先进后出的顺序排列。新元素被添加到堆栈顶部，而删除元素时也从顶部开始。

$n = 5;          // 要计算阶乘的数字
$stack = [$n];   // 用起始数字初始化堆栈
$result = 1;

while (!empty($stack)) {
    $current = array_pop($stack);
    $result *= $current;

    if ($current > 1) {
        $stack[] = $current - 1;  // 将下一个值推送到堆栈
    }
}

echo "Factorial of $n: $result\n";

解释：

简单来说，我们用堆栈来模拟递归函数调用过程，以实现阶乘计算。

模拟函数调用：就像递归函数会不断调用自身，并将参数传递给下一层调用一样，堆栈的作用就是存储这些参数，并模拟每次调用时传递的值。
迭代计算：我们从初始数字开始，将其压入堆栈。然后，通过循环不断从堆栈中弹出数字，并进行乘法运算。
继续迭代：当弹出的数字大于 1 时，我们将下一个数字 (current - 1) 推入堆栈，并继续这个循环，直到弹出 1 为止。

换句话说，堆栈中存储的是每次 "模拟递归调用" 的参数，我们通过循环进行迭代，并在每个迭代中模拟一次函数调用，直到完成计算。

2. 使用堆栈进行树遍历（深度优先搜索）

树遍历是指按照特定顺序访问树结构中所有节点的过程。深度优先搜索 (DFS) 是一种常用的树遍历策略，它从根节点开始，沿着每个分支尽可能深入地探索，直到遇到叶子节点，然后再回溯到上一层，继续探索其他分支。

本节将介绍使用堆栈来实现树遍历，而不使用递归。

$tree = [
    'value' => 1,
    'left' => [
        'value' => 2,
        'left' => null,
        'right' => null
    ],
    'right' => [
        'value' => 3,
        'left' => null,
        'right' => null
    ]
];

$stack = [$tree];
$values = [];

while (!empty($stack)) {
    $node = array_pop($stack);
    if ($node === null) {
        continue;
    }
    
    $values[] = $node['value'];
    
    // 将左右子节点推送到堆栈
    if (isset($node['right'])) $stack[] = $node['right'];
    if (isset($node['left'])) $stack[] = $node['left'];
}

echo "Depth-First Traversal: " . implode(', ', $values) . "\n";

解释：

我们使用堆栈来模拟深度优先搜索的过程。

压入堆栈：当我们访问一个节点时，我们将它的右子节点（如果有的话）先压入堆栈，然后是左子节点。这是为了确保我们在深度优先搜索中优先处理左子节点。
弹出并处理：我们从堆栈中弹出节点，并进行相应的处理，比如收集节点的值。
深度优先：由于右子节点先被压入堆栈，因此在处理完当前节点的左子节点后，我们才会回溯到父节点，并处理右子节点。这保证了我们按照深度优先的顺序遍历树。

换句话说，堆栈存储的是待访问的节点信息，我们通过弹出节点并进行处理，来模拟深度优先搜索的遍历过程。

3. 使用 goto 语句模拟递归（不推荐）

虽然 goto 语句在 PHP 中可用，但它通常不被推荐使用，因为它会导致代码难以理解和维护。然而，我们可以使用 goto 语句来模拟递归的行为，例如实现阶乘计算。

请注意，以下示例仅用于演示目的，不建议在实际开发中使用。

$n = 5;  // 计算阶乘的数
$result = 1;

start:
    if ($n <= 1) {
        echo "Factorial: $result\n";
        return;
    }

    $result *= $n;
    $n--;
    goto start;  // 跳回到 'start' 标签以继续“递归”过程