php 递归实现

PHP 递归实现方法

递归是一种函数调用自身的技术，适用于解决分治问题或需要重复处理相似子任务的情况。以下是PHP中递归的常见实现方式及注意事项。

基本递归结构

递归函数通常包含两个部分：基线条件（递归终止条件）和递归调用。以计算阶乘为例：

function factorial($n) {
    if ($n <= 1) { // 基线条件
        return 1;
    }
    return $n * factorial($n - 1); // 递归调用
}
echo factorial(5); // 输出120

目录遍历示例

递归常用于处理嵌套数据结构，如遍历目录及其子目录：

function scanDirectory($dir) {
    $files = scandir($dir);
    foreach ($files as $file) {
        if ($file != '.' && $file != '..') {
            $path = $dir . '/' . $file;
            if (is_dir($path)) {
                scanDirectory($path); // 递归处理子目录
            } else {
                echo $path . "\n";
            }
        }
    }
}
scanDirectory('/path/to/directory');

斐波那契数列

递归可解决数学序列问题，但需注意效率问题（可结合缓存优化）：

function fibonacci($n) {
    if ($n == 0) return 0;
    if ($n == 1) return 1;
    return fibonacci($n - 1) + fibonacci($n - 2);
}
echo fibonacci(10); // 输出55

递归优化技巧

• 尾递归优化：某些语言支持，但PHP不原生支持，可通过循环重构
• 记忆化技术：缓存已计算结果避免重复计算

$memo = [];
function fibonacciMemo($n) {
    global $memo;
    if (isset($memo[$n])) return $memo[$n];
    if ($n <= 1) return $n;
    $memo[$n] = fibonacciMemo($n - 1) + fibonacciMemo($n - 2);
    return $memo[$n];
}

注意事项

• 栈溢出风险：PHP默认调用栈深度约100-256层（可通过ini_set('xdebug.max_nesting_level', 1000)调整）
• 性能考量：递归可能比迭代效率低，尤其在未优化的情况下
• 明确终止条件：缺少基线条件会导致无限递归

递归转迭代

深度递归问题可改为使用栈结构的迭代方案：

function factorialIterative($n) {
    $result = 1;
    for ($i = 2; $i <= $n; $i++) {
        $result *= $i;
    }
    return $result;
}