php递归算法实现

PHP递归算法实现

递归是一种函数调用自身的编程技术，适用于解决可以分解为相似子问题的情况。PHP中实现递归算法需注意终止条件以避免无限循环。

基本递归结构

function recursiveFunction($param) {
    // 终止条件（Base Case）
    if ($condition) {
        return $value;
    }
    // 递归调用
    return recursiveFunction($modifiedParam);
}

阶乘计算示例

function factorial($n) {
    if ($n <= 1) {
        return 1;
    }
    return $n * factorial($n - 1);
}
echo factorial(5); // 输出120

斐波那契数列

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

目录遍历递归

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');

注意事项

递归深度过大可能导致栈溢出，PHP默认递归深度限制为100-256（取决于配置）。可通过ini_set('xdebug.max_nesting_level', 1000)调整，但更推荐改用迭代方案处理深层递归问题。

尾递归优化在PHP中不被原生支持，需手动转换为循环结构。例如阶乘的迭代实现：

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