php递归实现

递归的基本概念

递归是一种函数调用自身的技术，通常用于解决可以分解为相似子问题的情况。在PHP中，递归函数需要包含一个基本情况（终止条件）和一个递归情况（调用自身）。

简单的递归示例：阶乘计算

阶乘是递归的经典例子，n的阶乘（n!）定义为n(n-1)(n-2)...1。

function factorial($n) {
    if ($n <= 1) {
        return 1; // 基本情况
    } else {
        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');

递归的注意事项

递归可能导致栈溢出，尤其是处理深度较大的问题时。PHP默认的递归深度限制可通过ini_set('xdebug.max_nesting_level', 1000)调整，但需谨慎使用。

尾递归优化

某些语言支持尾递归优化，但PHP不原生支持。尾递归是指递归调用是函数的最后操作，可通过手动重构为循环来优化。

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

递归与迭代的选择

递归代码通常更简洁，但可能效率较低。对于性能敏感的场景，可考虑用循环替代递归。例如，阶乘的迭代实现：

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

实际应用场景

递归适合处理树形结构（如DOM、目录）、分治算法（如快速排序）或动态规划问题。使用时需确保终止条件明确，避免无限递归。