目錄

第一步：?我們要解決什么？

第二步：將其類比為求自然數和

第三步：什么是每一項？

第四步：定義要計算的每一項（term）

第五步：定義遞歸函數結構

?🌳 調用樹結構

完整代碼

復雜度分析?

🔚 總結圖（從定義到實現）：?

---

我們將用第一性原理來一步一步推導如何用 C++ 實現泰勒展開式（Taylor Series Expansion），并借助遞歸求自然數之和的思想進行類比和遷移。

第一步：?我們要解決什么？

我們要用 C++ 寫一個函數，計算 e^x?的近似值，基于泰勒展開公式。

第二步：將其類比為求自然數和

你已經知道：

int sumOfNumbers(int n)
{if (n == 0)return 0;elsereturn sumOfNumbers(n - 1) + n;
}

我們同樣可以將泰勒級數看作是：

f(x) = 第0項 + 第1項 + 第2項 + … + 第n項

所以我們可以嘗試用遞歸方法去表達每一項，累加所有項。

第三步：什么是每一項？

我們先思考“泰勒展開”的一項的數學結構：

我們從第一性原理推導出這個公式的兩部分組成：

• 分子是 x^n，也就是 x * x * x……（共n次）

• 分母是 n!=n * (n?1) * (n?2)?1

所以我們必須做兩件事：

• 每次遞歸都乘一次 x → 累計分子

• 每次遞歸都乘一次當前 n → 累計分母

從遞歸角度重新理解：

如果你在寫一個 taylor(n) 遞歸函數，你會每次調用去表示：

• 我要計算第 n?項，

• 第 n?項是第 n?1 項 * x?/?n

于是我們可以這樣遞推：

? 這個推導說明：

我們不需要單獨重復計算 x^n 和 n

我們可以利用上一步的結果，乘一個新的因子 x?/?n 就能得到下一項。

---

第四步：定義要計算的每一項（term）

?問題來了：

如果我們想用遞歸函數一步一步計算：

double taylor(int n, double x);

那么問題是：

• 上一項計算的結果在哪里？

• 本層計算需要的 x^(n-1) 和 （n-1）!怎么得來？

直覺嘗試：用返回值傳信息？

你可能會嘗試每次都重新計算 x^n?和 n!，像這樣：

double taylor(int n, double x) {return taylor(n-1, x) + pow(x, n) / factorial(n);  // NOT efficient
}

問題：

• 每一層都重復算一遍冪和階乘

• 沒有重用信息

? 真正的優化思路：我們需要“帶狀態的遞歸”

我們希望每次調用都記住前一項計算中積累出來的 x^n 和 n!

于是我們可以：

• 在函數內部保留靜態變量（或全局變量）

• 讓它在每一層遞歸中不斷更新

我們引入三個全局變量：

double num = 1; // 分子（x^n）
double den = 1; // 分母（n!）

每次遞歸做的事情就是：

• 分子（冪函數）乘上 x

• 分母（階乘）乘上 n

• 計算這一項 term = num / den

• 遞歸進入下一層（直到 n == 0 為止）

為什么不用局部變量？

• 每一層遞歸函數自己的局部變量在返回時會銷毀，狀態無法累積。

• 靜態/全局變量可以在整個遞歸調用鏈中持續保存狀態。

第五步：定義遞歸函數結構

我們遵循：

• 先處理“底部終止條件”（n == 0）

• 然后遞歸地構造前一項的和

• 最后處理當前這一項的貢獻

否則：你將會提早計算當前項（還沒到你這一層），狀態錯位。?

Step 1：遞歸函數要怎么“停下來”？

在定義任何遞歸函數的時候，必須先回答一個問題：

? 什么時候這個函數應該“終止”，不再遞歸？

這就是我們要設定的base case（基礎情況）。

在泰勒展開中，第 0 項是已知的常數 1，所以我們在 n=0 時應該返回：1

if (n == 0) return 1;

?? 這是遞歸的“錨點”，你必須先寫，否則遞歸會無限下去。

Step 2：遞歸要先“構造前面的和”

?思維實驗：

假設你現在寫的是：

double taylor(int n, double x) {num *= x;den *= n;double res = taylor(n - 1, x);return res + num / den;
}

你發現問題了沒？

你先更新了 num 和 den，然后才去計算上一項的結果，這就打亂了狀態的對應關系——因為上一

項本來是 x^(n-1) / (x-1) !，但你已經把它提前變成 x^n?/ x?!? 了。

錯誤：我們在進入上一個遞歸之前，就已經變更了狀態！

? 正確方式：

我們應該：

1. 先去計算 上一項的累加和（taylor(n - 1)）

2. 回來以后再更新狀態

3. 然后把當前這一項加進去

double taylor(int n, double x) {if (n == 0) return 1;double res = taylor(n - 1, x); // 🚶先去處理前面項num *= x;                      // ?回來再乘 xden *= n;                      // ?回來再乘 nreturn res + num / den;        // ?最后加上當前這一項
}

注意！這是典型的“遞歸先深入到底部（遞歸樹的葉子）”，然后在回溯的過程中逐層累計每一項。

?🌳 調用樹結構

示例：調用 taylor(3, x)，即展開 4 項 (n=3)

我們每調用一次函數，都畫出一層，并在返回時說明計算了哪一項。

                                taylor(3)↓taylor(2)↓taylor(1)↓taylor(0) ← base case = 1

然后回溯計算（從下向上）：

• 返回 taylor(0) = 1

• 回到 taylor(1)：

  • 分子 num *= x → x

  • 分母 den *= 1 → 1

  • 加項 x^1/1! = x

• 回到 taylor(2)：

  • num *= x → x2

  • den *= 2 → 2

  • 加項 x^2 / 2!

• 回到 taylor(3)：

  • num *= x → x3

  • den *= 3 → 6

  • 加項 x^3 / 3!

taylor(0) = 1
taylor(1) = taylor(0) + x / 1
taylor(2) = taylor(1) + x^2 / 2
taylor(3) = taylor(2) + x^3 / 6

回溯順序：
taylor(1) ← + x^1 / 1!     ← 分子: x，分母: 1
taylor(2) ← + x^2 / 2!     ← 分子: x2，分母: 2
taylor(3) ← + x^3 / 3!     ← 分子: x3，分母: 6

你看到沒，正是因為我們在回溯階段才處理當前項，才確保每一項都在它該在的位置！?

調用層	n	分子（num）	分母（den）	當前項?
3	3	x^3	3 !=6	x^3 / 6
2	2	x^2	2 !=2	x^2 / 2
1	1	x	1 !=1	x/1
0	0	1（初始值）	1（初始值）	1

完整代碼

double num = 1;  // 分子
double den = 1;  // 分母double taylor(int n, double x) {if (n == 0) return 1;               // 1?? 錨點：停止遞歸double res = taylor(n - 1, x);      // 2?? 先構造前面所有項的和num *= x;                           // 3?? 然后再更新狀態den *= n;return res + num / den;             // 4?? 當前項加進去
}

復雜度分析?

這是一個非常經典的線性遞歸（linear recursion）結構。我們來詳細分析其時間復雜度和空間復雜度。?

??時間復雜度分析（Time Complexity）

我們從函數調用過程來看：

• 調用 taylor(n) 會遞歸調用 taylor(n-1)

• taylor(n-1) 又會調用 taylor(n-2)

• ...

• 最后到底部 taylor(0) 返回 1，然后逐層回溯

整個遞歸鏈條是：

taylor(n)→ taylor(n-1)→ taylor(n-2)...→ taylor(0)

總共會調用 n+1 次函數（從 0 到 n）。

每一層遞歸執行的是：

• 一個函數調用（taylor(n - 1)）

• 兩次乘法：num *= x, den *= n

• 一次加法：res + num / den

這些操作都是常數時間 O(1)。

?? 所以：時間復雜度為：O（n）

空間復雜度分析（Space Complexity）

這就有趣了，因為這是遞歸。

你沒有使用堆內存（比如數組、鏈表），但遞歸函數本身會在調用棧上分配幀：

• 每調用一次 taylor(n)，系統會開辟一塊棧幀來保存：

  • 參數 n, x

  • 局部變量 res

  • 返回地址

由于這個是線性遞歸（不是尾遞歸），函數不會在遞歸過程中被優化掉（除非特別啟用尾遞歸優化，C++ 一般不保證）。

?? 所以：空間復雜度為：O（n）?

🔚 總結圖（從定義到實現）：?

數學定義：term_n = x^n / n!   ← 每一項都能用前一項 * (x/n) 得到遞歸目標：taylor(n) = taylor(n-1) + term_n中間狀態：num ← num * xden ← den * n于是代碼：num = 1;den = 1;double taylor(n, x) {if n==0 return 1;res = taylor(n-1, x);num *= x; den *= n;return res + num / den;}