当前位置：首页 > PHP

php 递归实现

2026-02-14 19:21:43PHP

PHP 递归实现的基本概念

递归是一种函数调用自身的技术，适用于解决可分解为相似子问题的情况。在 PHP 中，递归需明确终止条件，否则会导致无限循环或栈溢出。

php 递归实现

递归实现的要素

终止条件（Base Case）
递归必须有一个明确的终止条件，防止无限调用。例如，计算阶乘时，0 或 1 的阶乘为 1，此时终止递归。
递归调用（Recursive Call）
函数内部需调用自身，并逐步向终止条件逼近。例如，阶乘函数中调用 factorial($n - 1)。

示例：计算阶乘

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

递归的注意事项

性能问题：递归可能重复计算（如斐波那契数列），可用缓存（如静态变量）优化。
栈溢出：深度递归可能导致栈溢出，PHP 默认递归深度限制为 100-200 层（可通过 ini_set('xdebug.max_nesting_level', $limit) 调整）。

递归优化示例（带缓存的斐波那契）

function fibonacci($n, &$cache = []) {
    if ($n == 0 || $n == 1) {
        return $n;
    }
    if (!isset($cache[$n])) {
        $cache[$n] = fibonacci($n - 1, $cache) + fibonacci($n - 2, $cache);
    }
    return $cache[$n];
}

递归与迭代的选择

递归：代码简洁，适合树形结构（如目录遍历）。
迭代：性能更高，适合线性问题（可用循环替代递归）。

示例：目录遍历

function scanDirectory($dir) {
    $files = [];
    foreach (scandir($dir) as $file) {
        if ($file == '.' || $file == '..') continue;
        $path = $dir . '/' . $file;
        if (is_dir($path)) {
            $files = array_merge($files, scanDirectory($path)); // 递归子目录
        } else {
            $files[] = $path;
        }
    }
    return $files;
}

通过合理设计终止条件和递归逻辑，PHP 递归能高效解决分治类问题。

php 递归实现