C++ 斐波那契數列遞歸實現與程序流程圖繪製指南

遞歸算法核心

斐波那契數列定義：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n≥2)。遞歸實現極其簡潔但指數級時間複雜度 O(2^n)，僅適合教學演示 n≤30 場景。

標準遞歸代碼

#include 
using namespace std;

// 返回第 n 項 (0-based)
long long fib(int n) {
    if (n <= 1) return n;           // 基線條件
    return fib(n - 1) + fib(n - 2); // 遞歸步驟
}

int main() {
    int n;
    cout << "輸入項數 n (建議 ≤ 40): ";
    cin >> n;
    if (n < 0) return 1;
    for (int i = 0; i < n; ++i) {
        cout << "F(" << i << ") = " << fib(i) << endl;
    }
    return 0;
}

程序流程圖 (Program Flowchart) 繪製規範

流程圖使用標準符號 (ISO 5807 / GB/T 4722)：

主程序流程圖 (文字描述版)

[開始] (橢圓)
   ↓
[輸入 n] (平行四邊形)
   ↓
[初始化 i=0] (矩形)
   ↓
┌─→ [判斷 i < n?] (菱形) ──否──→ [結束] (橢圓)
│        ↓ 是
│   [調用 fib(i) 輸出結果] (矩形+平行四邊形)
│        ↓
│   [i = i + 1] (矩形)
│        ↓
└────────┘

遞歸函數 fib(n) 流程圖 (文字描述版)

[進入 fib(n)] (橢圓/矩形)
   ↓
[判斷 n <= 1?] (菱形)
   ├─ 是 → [返回 n] (矩形) → [函數返回] (橢圓)
   └─ 否 → [計算 fib(n-1)] (矩形/調用)
            ↓
         [計算 fib(n-2)] (矩形/調用)
            ↓
         [返回 fib(n-1)+fib(n-2)] (矩形)
            ↓
         [函數返回] (橢圓)

繪圖工具推薦

• 在線：draw.io (diagrams.net)、ProcessOn、Mermaid Live Editor (代碼生成圖)
• 桌面：Visio、EdrawMax、XMind (思維導圖模式)、PlantUML (IDE 插件)
• Mermaid 代碼示例 (可直接貼入 Markdown/Notion/GitHub)：

  
  flowchart TD
      A([開始]) --> B[/輸入 n/]
      B --> C[i = 0]
      C --> D{i < n?}
      D -- 否 --> Z([結束])
      D -- 是 --> E[調用 fib(i) 輸出]
      E --> F[i = i + 1]
      F --> D
      
      subgraph fib_avoid_recursion [fib(n) 遞歸邏輯]
          G([fib(n)]) --> H{n <= 1?}
          H -- 是 --> I[返回 n]
          H -- 否 --> J[調用 fib(n-1)]
          J --> K[調用 fib(n-2)]
          K --> L[返回 fib(n-1)+fib(n-2)]
      end
  

性能陷阱與優化 (必考加分項)

迭代 O(1) 空間版 (工程首選)

long long fib_iter(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

結語

遞歸斐波那契是理解遞歸基線條件、調用棧、重複子問題的絕佳教具；流程圖則訓練結構化思維、控制流可視化能力。實際工程中請務必使用迭代或矩陣快速冪。掌握從「遞歸定義」到「流程圖」再到「優化實現」的完整鏈路，是算法入門的關鍵一課。