PHP树遍历性能对比：递归函数VS自定义栈循环

测试代码与结果 #

function recurse(array $tree) {
    foreach($tree as $subtree) {
        if(!is_array($subtree)) {
            do_some_thing($subtree);
        } else {
           recurse($subtree);
        }
    }
}

function dfs(array $tree) {
    $stack = [$tree];
    while (!empty($stack)) {
        $subtree = array_pop($stack);
        if(!is_array($subtree)) {
            do_some_thing($subtree);
        } else {
            for ($i = count($subtree) - 1; $i >= 0; $i --) {
                $stack[] = $subtree[$i];
            }
        }
    }
}

// 测试辅助函数
function do_some_thing($node) {
    echo $node;
}

// 递归执行耗时（5次测试）：
// 0.000156s
// 0.000163s
// 0.000157s
// 0.000168s
// 0.000143s

// 自定义栈DFS执行耗时（5次测试）：
// 0.000293s
// 0.000201s
// 0.001716s
// 0.000335s
// 0.000169s

测试显示递归版本recurse()耗时稳定且更快，自定义栈的dfs()不仅平均速度慢，还出现大幅波动的异常值，和“系统栈开销大于自定义栈”的预期相反，以下是具体分析：

一、递归反而更快的原因 #

1. PHP底层递归优化：PHP的递归调用栈由底层C实现，栈帧的创建、销毁和切换效率远高于PHP层面用数组模拟的栈操作。自定义栈的array_pop、循环压栈等操作都要经过PHP解释器层层处理，额外开销更大。
2. 循环效率差异：递归版本使用foreach遍历子树，foreach是PHP中高度优化的循环结构，直接操作内部数组指针，效率比自定义栈中手动的for循环+索引访问高很多。
3. 测试规模局限性：你用的测试树结构极小，递归深度仅3层左右，此时系统栈开销可忽略不计，反而自定义栈的数组操作开销被放大。那次0.001716s的异常值，大概率是测试时PHP垃圾回收、进程调度等外部因素干扰，小样本下递归的稳定性源于操作逻辑更简洁。

二、该现象是否普遍？ #

在PHP中，小到中等规模的树结构下，递归比手动栈实现更快是普遍现象：

• 对比Python、Java等语言，手动栈在递归深度较大时可能更有优势，但PHP的递归栈由底层优化，而数组作为哈希表的操作开销较高，导致手动栈的优势无法体现。
• 只有当递归深度超过PHP默认嵌套限制（xdebug.max_nesting_level默认100）时，递归会触发报错，此时必须使用自定义栈，这种场景下不存在性能对比的前提。

三、大规模树结构下的性能差异 #

当树结构深度极大（比如上千层）或节点数量过亿时：

1. 递归的局限性：递归会直接触发栈溢出错误，即使调整PHP的栈限制参数，也会导致内存占用线性增长，最终引发内存溢出，此时只能使用自定义栈实现。
2. 性能反转的可能：极端大规模场景下，递归的栈帧开销会持续累积，而自定义栈的数组操作开销会被分摊，两者的性能差距会逐渐缩小，甚至自定义栈可能反超。但这种场景在PHP业务开发中极少遇到，因为PHP本身不是为处理超大规模内存数据设计的。

内容的提问来源于stack exchange，提问作者cr001