PHP 递归函数怎么将递归算法转为迭代写法-php教程-PHP中文网

递归转迭代不是简单去掉函数调用，而是必须手动模拟调用栈来保存参数、局部变量和返回位置；否则会导致逻辑错乱、重复处理或无法回溯。

php 递归函数怎么将递归算法转为迭代写法

为什么递归转迭代不是简单“去掉 function 调用”

递归函数依赖调用栈自动保存每层的状态（如参数、局部变量、返回位置），而迭代必须手动模拟这个栈。直接删掉 self::func() 或 func($next)，不补上状态管理逻辑，结果一定是逻辑错乱或无限循环。

常见错误现象包括：漏掉某一层子节点、重复处理同一节点、无法回溯父级上下文（比如树路径拼接失败）。关键不在“怎么写循环”，而在“每次循环该压入什么、弹出什么、用什么变量承接中间结果”。

PHP 中用数组模拟栈实现树遍历的典型写法

以遍历多维嵌套数组（类似无限极分类）为例，递归写法常是：

function traverse($arr) {
    foreach ($arr as $item) {
        echo $item['name'];
        if (!empty($item['children'])) {
            traverse($item['children']);
        }
    }
}

对应迭代写法需显式维护一个待处理节点栈：

初始化栈为根节点数组（[$root] 或整个输入数组）
循环中 array_pop() 取出当前节点，处理其数据
若存在子节点，把它们 array_unshift() 或 array_push() 进栈（注意顺序影响遍历方向）
用普通变量（如 $path）记录路径，每次进入新节点时拼接，退出时截断——这一步没有自动栈帧，必须手动管理

示例片段（深度优先、正向输出）：

$stack = [$data];
while (!empty($stack)) {
    $node = array_pop($stack);
    echo $node['name'] . "\n";
    if (!empty($node['children'])) {
        // 保证 children 从右到左入栈，才能维持原递归顺序
        foreach (array_reverse($node['children']) as $child) {
            array_push($stack, $child);
        }
    }
}

遇到闭包或带状态的递归函数怎么办

如果原递归函数还依赖外部变量（如计数器 $depth、累加器 $sum、引用参数 &$result），这些都不能靠栈自动携带。必须把它们打包进栈元素本身。

例如计算树最大深度的递归：

btpanel phpsite 宝塔面板PHP网站

宝塔面板 PHP 网站管理：站点创建、删除、启停、PHP 版本切换、域名管理、SSL证书管理、伪静态管理、数据库管理

下载

function maxDepth($node, $depth = 1) {
    if (empty($node['children'])) return $depth;
    $max = $depth;
    foreach ($node['children'] as $child) {
        $max = max($max, maxDepth($child, $depth + 1));
    }
    return $max;
}

迭代改写时，栈中每个元素应是关联数组：['node' => $child, 'depth' => $current_depth + 1]：

$stack = [['node' => $root, 'depth' => 1]];
$maxDepth = 1;
while (!empty($stack)) {
    $item = array_pop($stack);
    $maxDepth = max($maxDepth, $item['depth']);
    foreach ($item['node']['children'] as $child) {
        array_push($stack, ['node' => $child, 'depth' => $item['depth'] + 1]);
    }
}

这里容易踩的坑：用两个独立数组分别存 $nodes 和 $depths，极易因 push/pop 不同步导致错位；必须绑定成结构化单元。