php实现递归

递归的基本概念

递归是一种函数调用自身的技术，适用于解决可以分解为相同子问题的问题。在PHP中，递归需要明确的终止条件（基线条件），否则会导致无限循环。

递归实现阶乘

阶乘是经典的递归案例，n! = n * (n-1)!，终止条件为n = 1时返回1。

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默认递归深度约100-200层，超出会报错，可通过ini_set('xdebug.max_nesting_level', 1000)调整。

尾递归优化

PHP不支持自动尾递归优化，但可通过循环或手动优化减少栈消耗。例如改写阶乘函数：

function factorialTail($n, $accumulator = 1) {
    if ($n <= 1) return $accumulator;
    return factorialTail($n - 1, $n * $accumulator);
}