遞歸是解決「問題可分解為相同性質的子問題」的經典技術。本文以1到N自然數求和為例,講解PHP遞歸實現、執行流程、棧溢出風險及尾遞歸優化方案。
function summation($count) {
if ($count != 0) {
return $count + summation($count - 1);
}
return 0; // 隱含基準情況
}
$sum = summation(10); // 55
echo "Summation = $sum";
summation(10) → 10 + summation(9) → ... → 1 + summation(0) → 0 → 逐層返回累加。
$count > 10000左右即會報錯Maximum function nesting level。function sum_iterative($n) {
$total = 0;
for ($i = 1; $i <= $n; $i++) {
$total += $i;
}
return $total;
}
function summation_tail($n, $acc = 0) {
if ($n === 0) return $acc;
return summation_tail($n - 1, $acc + $n);
}
// 仍受棧限制,生產環境建議用迴圈
function sum_formula($n) {
return $n * ($n + 1) / 2;
}
遞歸適合樹遍歷、分治算法(快排、歸併排序)、圖搜索(DFS)等結構性問題。簡單累加優先用迴圈或公式。