php函数使用递归实现
递归的基本概念
递归是一种函数调用自身的技术，通常用于解决可分解为相似子问题的情况。递归函数必须包含基线条件（停止条件）和递归条件（调用自身的条件），否则可能导致无限循环。
PHP递归函数示例
计算阶乘
阶乘（n!）是典型的递归案例，定义如下：
- 基线条件：0! = 1
- 递归条件：n! = n × (n-1)!
function factorial($n) {
if ($n === 0) { // 基线条件
return 1;
} else { // 递归条件
return $n * factorial($n - 1);
}
}
echo factorial(5); // 输出 120斐波那契数列
斐波那契数列（F(n) = F(n-1) + F(n-2)）也可用递归实现：
- 基线条件：F(0) = 0，F(1) = 1
- 递归条件：F(n) = F(n-1) + F(n-2)
function fibonacci($n) {
if ($n === 0) {
return 0;
} elseif ($n === 1) {
return 1;
} else {
return fibonacci($n - 1) + fibonacci($n - 2);
}
}
echo fibonacci(6); // 输出 8递归的注意事项
- 性能问题：递归可能重复计算子问题（如斐波那契数列），可通过记忆化（缓存结果）优化。
- 栈溢出：深度递归可能导致调用栈溢出，需合理设置基线条件或改用迭代。
优化斐波那契（记忆化）
function fibonacciMemo($n, &$memo = []) {
if (isset($memo[$n])) return $memo[$n];
if ($n === 0) return 0;
if ($n === 1) return 1;
$memo[$n] = fibonacciMemo($n - 1, $memo) + fibonacciMemo($n - 2, $memo);
return $memo[$n];
}
echo fibonacciMemo(50); // 快速计算大数值递归与迭代的选择
- 递归：代码简洁，适合问题天然递归（如树遍历）。
- 迭代：效率更高，适合深度大或需避免重复计算的场景。
阶乘的迭代实现
function factorialIterative($n) {
$result = 1;
for ($i = 1; $i <= $n; $i++) {
$result *= $i;
}
return $result;
}
