php递归算法实现

PHP递归算法实现

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

基本递归结构

递归函数通常包含两部分：基线条件（终止条件）和递归条件（调用自身）。以下是一个计算阶乘的示例：

function factorial($n) {
    if ($n <= 1) { // 基线条件
        return 1;
    } else { // 递归条件
        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');

斐波那契数列

斐波那契数列是经典递归案例，但需注意效率问题：

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

递归优化

递归可能引发性能问题，可通过记忆化（缓存结果）优化：

$cache = [0 => 0, 1 => 1];
function fibonacciMemo($n) {
    global $cache;
    if (!isset($cache[$n])) {
        $cache[$n] = fibonacciMemo($n - 1) + fibonacciMemo($n - 2);
    }
    return $cache[$n];
}

注意事项

递归深度受PHP配置限制，可通过ini_set('xdebug.max_nesting_level', 200)调整。对于深层递归，建议改用迭代实现。递归应始终有明确的终止条件，避免栈溢出。