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 递归能高效解决分治类问题。
