萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP遞歸函數實現數字累加:原理、實現與優化

遞歸是解決「問題可分解為相同性質的子問題」的經典技術。本文以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 → 逐層返回累加。

潛在問題

  • 棧溢出:PHP默認棧大小有限,$count > 10000左右即會報錯Maximum function nesting level。
  • 性能開銷:每次調用分配棧幀,較迴圈慢。

優化方案

1. 迴圈迭代(推薦)

function sum_iterative($n) {
    $total = 0;
    for ($i = 1; $i <= $n; $i++) {
        $total += $i;
    }
    return $total;
}

2. 尾遞歸(PHP不原生優化,但可手動轉迴圈)

function summation_tail($n, $acc = 0) {
    if ($n === 0) return $acc;
    return summation_tail($n - 1, $acc + $n);
}
// 仍受棧限制,生產環境建議用迴圈

3. 數學公式(O(1))

function sum_formula($n) {
    return $n * ($n + 1) / 2;
}

適用場景

遞歸適合樹遍歷、分治算法(快排、歸併排序)、圖搜索(DFS)等結構性問題。簡單累加優先用迴圈或公式。

copyright © 萬盛學電腦網 all rights reserved