php 递归实现

递归的概念

递归是一种在函数内部调用自身的技术，通常用于解决可以被分解为相似子问题的问题。在PHP中，递归函数需要设置一个基线条件（终止条件），以避免无限循环。

基本递归实现

以下是一个简单的递归函数示例，计算一个数的阶乘：

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

echo factorial(5); // 输出: 120

目录遍历递归

递归常用于遍历目录结构，以下是递归遍历目录并列出所有文件的示例：

function listFiles($dir) {
    $files = scandir($dir);
    foreach ($files as $file) {
        if ($file != '.' && $file != '..') {
            $path = $dir . '/' . $file;
            if (is_dir($path)) {
                listFiles($path); // 递归调用
            } else {
                echo $path . "\n";
            }
        }
    }
}

listFiles('/path/to/directory');

递归的注意事项

递归函数需要谨慎设计，避免栈溢出或性能问题。确保基线条件能够被满足，递归调用能够逐步接近基线条件。

尾递归优化

PHP不直接支持尾递归优化，但可以通过循环或迭代方式模拟。以下是阶乘函数的尾递归实现：

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

echo factorialTail(5); // 输出: 120

递归与迭代的选择

递归代码通常更简洁，但可能消耗更多内存。对于深度较大的问题，建议使用迭代替代递归。