# [CS:APP](https://hackmd.io/c/S1vGugaDQ/) 第 5 章重點提示和練習 :::success 資料整理: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) :warning: 最佳化來自對系統的充分認知 ::: ## Optimization * [最佳化 vs. 優化](https://www.ptt.cc/bbs/Soft_Job/M.1347718409.A.28B.html) * 國家教育研究院: [optimize](http://terms.naer.edu.tw/detail/2403595/) * 最佳化;最優化;優選 * 最佳化之前,務必確保「正確」,否則一切皆是徒勞 * YouTube: [圍棋的走法和宇宙原子總量誰更多?](https://www.youtube.com/watch?v=EidjMIlQ3x4) * [費馬大定理](https://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%A4%A7%E5%AE%9A%E7%90%86) (1995 年,Andrew Wiles 證明定理成立): 當整數 n> 2時,關於 x, y, z 的不定方程式 x^n^ + y^n^ = z^n^ 沒有正整數解,但如果拿計算機,用 x = 3987, y = 4365, n = 12 帶入 ![](https://i.imgur.com/TsLrxRu.png) * 好像可以推翻費馬大定理?這是計算機能表達的有效位數有限,等式左邊只比右邊大 0.000000002% ! :::info YouTube: [羅輯思維 85 集: 費馬大定理](https://www.youtube.com/watch?v=bHexlr4b_j8) * 我們當中的絕大多數人,花了人生的十二年時光,六年小學,六年中學,被數學摧殘,我們只知道數學是敲開大學校門的一個敲門磚,自打上了大學之後,這個東西就被我們當做人生當中最痛苦的經驗,被刪除了。 * 原來數學是如此有魅力,它的魅力是光芒萬丈,吸引那麼多智力卓絕的人,把自己的生命獻祭上去,整個數學史,就是一曲波瀾壯闊的史詩。 * 人類知識領域智力領域的任何豐碑,從來都不是用強烈的目的性建造出來的,它的每一塊磚,每一塊瓦,都是由興趣堆積出來的,興趣不僅導致了最後的成功,而且點亮了其中的每一塊磚,每一塊瓦,每一個人的生命。 ::: * 1946 年就有 binary search 的概念,但到了 1960 年代才有精準的數學分析,而到了 1980/1990 年代,大型系統中的 [binary search 實作的錯誤才被找出](https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues) * [Binary Search](https://locklessinc.com/articles/binary_search/) ## Code Optimization * 導讀 * [你所不知道的 C 語言:編譯器和最佳化原理篇](https://hackmd.io/s/Hy72937Me) * [你所不知道的 C 語言:動態連結器篇](https://hackmd.io/s/HkK7Uf4Ml) :::info [slides](https://www.cs.cmu.edu/~213/lectures/10-optimization.pdf) ::: asymptotic [/ˌæs.ɪmˈtɑː.t̬ɪk] 漸近的 ![](https://i.imgur.com/lIWkWQW.png) 最佳化編譯器的重要性 ![](https://i.imgur.com/U1Whdxw.png) Code Motion * 原本的程式碼 ```C void set_row(double *a, double *b, long i, long n) { for (long j = 0; j < n; j++) a[n * i + j] = b[j]; } ``` * 轉換為以下: (避免重複的 `n * j` 運算) ```C long j; int ni = n * i; for (j = 0; j < n; j++) a[ni + j] = b[j]; ``` 但要注意以下不適用 code motion 的例外狀況: * C 指標作為參數傳入,見 [From Source to Binary](https://www.slideshare.net/jserv/how-a-compiler-works-gnu-toolchain) Page 36 ~ 38 * [CS:APP 第 2 章提及的浮點數操作議題](https://hackmd.io/s/rJoxSsiuG) ![](https://i.imgur.com/nHCUraz.png) 可見到 C 的 array subscripting 會被替換為對應指標操作 ![](https://i.imgur.com/ql4Cqie.png) 2009 年的 [Nehalem](https://en.wikipedia.org/wiki/Nehalem_(microarchitecture)) (採用 45 奈米製程,後期改用 32 奈米製程); 2013 年的 [Haswell](https://en.wikichip.org/wiki/intel/microarchitectures/haswell_(client)) (和 Ivy Bridge 微架構一樣採用 22 奈米製程) * 延伸閱讀 [CS:APP3 第 6 章](https://hackmd.io/s/H1vQ3vu2z),提及記憶體操作的成本 [common subexpression elimination](https://en.wikipedia.org/wiki/Common_subexpression_elimination) (CSE) ![](https://i.imgur.com/bFMg6gy.png) Optimization Example: Bubblesort * slide 10-18 Procedure to Convert String to Lower Case ==Page 351== * slide 21-26 * 延伸閱讀: [Re: [問卦] C程式大神們請進](https://disp.cc/b/163-adct) ```C static const int ascii_x = 32; /* Lower to Upper Case; Upper to Lower Case */ static inline char *case_swap(char *in) { for (int i = 0; in[i] != '\0'; i++) if (isalpha(in[i])) in[i] ^= ascii_x; return in; } ``` ![](https://i.imgur.com/BuNIeG8.png) [你所不知道的 C 語言:動態連結器篇](https://hackmd.io/s/HkK7Uf4Ml) 提及 LTO (Link Time Optimization),有機會對這類案例進行最佳化,但現有技術仍有相當多限制 ![](https://i.imgur.com/qkva0Sw.png) 延伸閱讀: [strict aliasing](http://blog.tinlans.org/2010/01/09/strict-aliasing/) * 考慮以下程式碼: ```C= void foo(int *v1, int *v2, int *result, int count) { while(count--) { *result += *v1 + *v2; } } ``` * 大部分的人都以為編譯器為了做最佳化,會去把 `*v1 + *v2` 的算式往迴圈外面提,然後將 `*v1 + *v2` 的結果存到一個暫時變數上,再把迴圈裡的算式直接用那個暫時變數代換以節省重複運算的時間。不過這是不對的! * 因為編譯器不知道會不會有人寫 foo(&var, &var, &var, 1000) 來呼叫 foo,所以會假設所有的 pointer 之間都有 aliasing。 * 簡單說就是假設 *result 被改變了,那麼 *v1 和 *v2 的值也會跟著改變 * 所以不能像上面那樣把 *v1 + *v2 的結果視為 [loop invariant](https://en.wikipedia.org/wiki/Loop_invariant),必須每一次重新計算才行 * 更精確的來說,就是每個 iteration 都要把 *v1 和 *v2 的值從 memory 裡重新 load 出來 (有點類似 volatile 變數的行為),所以會對執行時期效能有影響 * 當然 strict aliasing 的標準化並不能解決上述的效能問題。 * 上述問題的解法是使用 C99 的 restrict 去修飾 pointer 的 type,==由程式開發者來保證==它們之間絕對不會有 aliasing,讓 compiler 放心的去做最佳化 :::info loop invariant 是證明某個不變的條件 (稱做 invariant Condition),這個條件在程式進入迴圈前跟進入迴圈後,此條件仍不變。 以 while 迴圈為例: ```C while (A) { // Body } ``` 假設一個 invariant 條件叫做 `X` ,這個 `X` 條件在 while 檢查 A 條件時都維持原狀,一進入 Body 時可能改變 `X` 條件,但一執行完 Body 後 X 又恢復原貌,這種條件就是一個典型的 invariant condition。 證明 loop invariant 需要 3 步驟: 1. initialization: 描述 invariant condition 在迴圈執行第一個 iteration 前,就成立; 2. maintenance: 描述 invariant condition 在迴圈的任一 iteration 執行前跟執行後都維持成立; 3. termination:迴圈執行結束後,invariant condition 能夠展示整體演算法的正確性; ::: strict-aliasing 衍生的型態問題非常複雜,可見 [C99 and type-punning – making sense of a broken language specification](https://davmac.wordpress.com/2010/02/26/c99-revisited/) 和 [Understanding Strict Aliasing](https://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html) 考慮以下程式碼: ```C void f(){ *((int *) 0xBAD) = 123; } ``` 地址 0xBAD 的內容會是什麼? > `0xBAD` 這樣用 16 進位數值表達特定人類可理解的意思,稱為 [hexspeak](https://en.wikipedia.org/wiki/Hexspeak) 延伸閱讀: [The Meaning of Memory Safety](https://arxiv.org/pdf/1705.07354.pdf) 這也讓許多 C subset/extension 存在,例如 [Cyclone](https://en.wikipedia.org/wiki/Cyclone_(programming_language)) ![](https://i.imgur.com/WkOM515.png) Cycles Per Element (CPE) ==Page 345== 考慮到以下向量運算操作的程式碼: ==Page 347== ```C /* data structure for vectors */ typedef struct { size_t len; data_t *data; } vec; /* retrieve vector element and store at val */ int get_vec_element(*vec v, size_t idx, data_t *val) { if (idx >= v->len) return 0; *val = v->data[idx]; return 1; ``` ![](https://i.imgur.com/XjQQuRJ.png) ![](https://i.imgur.com/oUC2goy.png) 如果我們施加以下最佳化手段: * 將 `vec_length` 搬出迴圈 * 避免每次運算都要檢查邊界範圍 (將函數 `get_vec_element` 從迴圈中拿出來,CPE 基本上沒有改變,因爲這些檢測總是預測索引是在界內的,所以是高度可預測的) * 消去重複的運算 ![](https://i.imgur.com/V62ZS0v.png) 除了上述和處理器架構無關的最佳化,事實上進階最佳化手段往往鎖定現代處理器的特徵: ==Page 357== ![](https://i.imgur.com/e2h51UX.png) - [ ] Superscalar Processor ==Page 360== - [ ] Loop Unrolling - [ ] SIMD ==Page 376== - [ ] Branch Prediction ==Page 379== 回頭閱讀 [CS:APP 第 4 章](https://hackmd.io/s/ByKFm4CFz) 以學習計算機結構。 - [ ] 減少記憶體存取 考慮以下加總函式,而 `ret` 為返回地址: * sum1 ```C void sum1(int *a, int len, int *ret) { *ret = 0; for (int i = 0; i < len; i++) *ret += a[i]; } ``` * sum2 ```C void sum2(int *a, int len, int *ret) { int s = 0; for (int i = 0; i < len; i++) s += a[i]; *ret = s; } ``` 兩個函式的功能完全一樣,而且 sum1 也來得更直觀些,sum2 有時就會讓人不解為何要引入一個中間變數 s 來保存累加和。 反組譯這兩段程式碼: * sum1 ```C movl (%edi), %eax imull (%ecx, %edx, 4), %eax mov %eax, (%edi) ``` * sum2 ```C imull (%ecx, %edx, 4), %eax ``` sum1 中對 ret 的 deference 會導致從 `%edi (ret)` 的地址中取值 (*ret) 指派給 `%eax`,然後再從 `%eax` 指定回( %edi) 這個過程。而循環 len 次就會多出 2 * len 道指令。所以 sum2 的效率要高,那麼高多少呢,在 Intel Core i5 M520 2.40GHz 做實驗可得: ![](https://i.imgur.com/bEAx5hv.jpg) 注意,這裡的時間單位是 ms (10^-3^s, 讀作 [Milliseconds](https://www.timecalculator.net/milliseconds-to-seconds))。當 len 的長度不斷以 10 的數量級遞增時,`sum2` 的時間優勢其實並不明顯。在 len = 10^8^ 時,差距僅僅是 140 ms(加速因子k = 1.34, k = sum1 時間 / sum2 時間),得益於現代硬體架構的進化,如此效能差距會縮減。 - [ ] Loop Unrolling 對 sum1 函式的進一步優化: ```C void sum3(int *a, int len, int *ret) { int s = 0; int limit = len - 2; int i; for (i = 0; i < limit; i += 3) s += a[i] + a[i + 1] + a[i + 2]; for ( ; i < len; i++) s += a[i]; *ret = s; } ``` ![](https://i.imgur.com/c67M2Tu.jpg) len = 10^8^ 時,sum3 相對於 sum2 縮減 172ms (k = 1.74),相對 sum1 縮減 312ms (k = 2.33)。為什麼會有這種提高?可以看到在循環中步長變為了3,那麼為什麼要是 3 而不是其他呢? 這就需要理解計算機結構。 ![](https://i.imgur.com/zweS7KR.png) 理想的計算機中 (例如 Alan Turing 的抽象機器),硬體資源可以是無窮無盡,於每個週期我們都有無限的計算器件可用。看到在第三週期用到了 `jl`, `cmpl`, `incl` 硬體資源,但其實都要用到加法器。 反過來看,真實計算機的硬體資源也不可能無限多。考慮到只能有兩個加法器的狀況,在同一週期,我們只能有兩個涉及加法的指令。那麼就有了如下的現實中的計算版本。顯然效率要比理想版本差,效率拖後約 1 倍。 ![](https://i.imgur.com/hTjEciQ.png) 如何用手頭有限的資源創造最大的效益,就是最佳化的策略。load 指令的週期是一般指令的 3倍,而 load 可以 pipeline 執行,那麼儘量讓 load 做事,就是我們所期望的改進。於是就有上述的 `sum3`: ![](https://i.imgur.com/D3oSsZN.png) 目的很明顯,儘量減少 `addl`, `cmpl` 和 `jl` 這些指令的執行,這樣就不至於太受加法器資源的限制,另外儘量利用 load 的 pipeline 執行特性。那麼如何減少 `jl` 的執行呢?終於想到了加大每次步長了吧。又為什麼是 3 呢?想到了load的週期是 3 了吧。謎團終於解開,看看最終版本的 sum3 是如何在機器中執行的: ![](https://i.imgur.com/9b0788u.png) 看到 3 步一循環的方法能有效地降低 `jl` 的執行,同時充分地利用了load 的 pipeline 特性。最後,這個版本相對理想版本效率拖後約 0.33倍。 既然能增加性能又為什麼要謹慎呢?問題是,以後呢?再以後呢?讓我們看得遠一點,再遠一點。硬件的發展總是如此之快,加法器會有的,load 會更快的。然後呢,然後就是,你做的優化還得隨著硬體不斷修正。 - [ ] Loop Splitting 繼續 sum1 的討論,如果我們把加法操作改為乘法呢? ```C void multi1(int *a, int len, int *ret) { *ret = 1; for (int i = 0; i < len; i++) *ret *= a[i]; } ``` 書本給予一種最佳化實作: ```C void multi2(int *a, int len, int *ret) { int limit = len - 1; int m0 = 1; int m1 = 1; int i; for (i = 0; i < limit; i += 2) { m0 *= a[i]; m1 *= a[i + 1]; } for ( ; i < len; i++) m0 *= a[i]; *ret = m0 * m1; } ``` m0 計算偶數下標的乘積,而 m1 計算奇數下標。最後合併。看看到底有多快: ![](https://i.imgur.com/mSibi9U.png) Len = 10^8^,差異 140ms, k = 1.43。另外,由於之前的 loop unrolling 也基本上能猜出個大概了。乘法器件耗費的週期巨大,又由於其 pipeline 特性。所以考慮增加每次循環中的乘法次數,而不必等到乘積結果迭代到下次而產生的延時。 ![](https://i.imgur.com/IcwV01D.png) 重點提示: 1. 減少對相同函式的呼叫,用一個變數保存返回值 2. 對於隱性增加複雜度的系統函數,特別是在循環中的函式要注意 3. 指標操作所引起的一些意想不到的效果,該再三留意; 4. 利用 profiler 來分析程式瓶頸,著重優化瓶頸函式; ==Page 388== 5. [Amdahl's law](https://en.wikipedia.org/wiki/Amdahl%27s_law) * [具象解釋](https://chi_gitbook.gitbooks.io/personal-note/content/amdahls_law.html) * [CS:APP3e-labs Performance Lab 解題報告](http://zxcpyp.com/csapp/2017/11/19/Performance-Lab) / [Performance Lab 筆記](https://github.com/Exely/CSAPP-Labs/blob/master/notes/perflab.md) * 要求你優化兩個圖片處理函數 * rotate: 把圖片逆時針旋轉 90° * smooth: 使圖片變平滑 ``` Rotate: Version = rotate() function: Dim 64 128 256 512 1024 Mean Your CPEs 2.6 2.8 3.9 5.6 8.3 Baseline CPEs 14.7 40.1 46.4 65.9 94.5 Speedup 5.6 14.5 12.0 11.8 11.3 10.5 Smooth: Version = smooth() function: Dim 32 64 128 256 512 Mean Your CPEs 19.3 21.7 21.9 22.1 17.8 Baseline CPEs 695.0 698.0 702.0 717.0 722.0 Speedup 36.1 32.1 32.1 32.5 40.6 34.5 ``` ## 遞迴與最佳化 電腦程式中,副程式直接或間接呼叫自己就稱為遞迴。遞迴算不上演算法,只是程式流程控制的一種。程式的執行流程只有兩種: * 循序,分支(迴圈) * 呼叫副程式(遞迴) 迴圈是一種特別的分支,而遞迴是一種特別的副程式呼叫。 不少初學者以及教初學者的人把遞迴當成是複雜的演算法,其實單純的遞迴只是另一種函數定義方式而已,在程式指令上非常簡單。初學者為什麼覺得遞迴很難呢?因為他跟人類的思考模式不同,電腦的兩種思維模式:窮舉與遞迴(enumeration and recursion),窮舉是我們熟悉的而遞迴是陌生的,而遞迴為何重要呢?因為他是思考好的演算法的起點,例如分治與動態規劃。 分治:一刀均分左右,兩邊各自遞迴,返回重逢之日,真相合併之時。 分治 (Divide and Conquer) 是種運用遞迴的特性來設計演算法的策略。對於求某問題在輸入 S 的解 P(S) 時,我們先將 S 分割成兩個子集合 S~1~ 與 S~2~,分別求其解 P(S~1~) 與 P(S~2~),然後再將其合併得到最後的解 P(S)。要如何計算 P(S~1~) 與 P(S~2~) 呢?因為是相同問題較小的輸入,所以用遞迴來做就可以了。分治不一定要分成兩個,也可以分成多個,但多數都是分成兩個。那為什麼要均分呢?從下面的舉例說明中會了解。 從一個非常簡單例子來看:在一個陣列中如何找大最大值。迴圈的思考模式是:從前往後一個一個看,永遠記錄著目前看到的最大值。 ```Clike m = a[0]; for (i = 1 ; i < n; i++) m = max(m, a[i]); ``` 分治思考模式:如果我們把陣列在i的位置分成前後兩段 a[0, i - 1] 與 a[i, n],分別求最大值,再返回兩者較大者。切在哪裡呢?如果切在最後一個的位置,因為右邊只剩一個無須遞迴,那麼會是 ```C int find_m1(int n) { if (n == 0) return a[0]; return max(find_m1(n - 1), a[n]); } ``` 這是個尾遞迴 (Tail Recursion),在有編譯優化的狀況下可跑很快,其實你可以發現他的行為就是上面那個迴圈的版本。如果我們把他切在中點: ```C int find_m2(int left, int right) { // 範圍=[ left,right) 慣用左閉右開區間 if (right - left == 1) return a[left]; int mid = (left + right) / 2 ; return max(find_max(left, mid), find_max(midi, right); } ``` 效率一樣是線性時間,會不會遞迴到 stack overflow 呢?放心,如果有200 層遞迴陣列可以跑到 2^200^,地球已經毀滅了。 再來看個有趣的問題:假設我們有一個程式比賽的排名清單,有些選手是女生有些是男生,我們想要計算有多少對女男的配對是男生排在女生前面的。若以 0 與 1 分別代表女生與男生,那麼我們有一個 0/1 序列 a[n],要計算 ``` Ans = | {(a[i], a[j]) | i < j 且 a[i] > a[j]} | ``` 迴圈的思考方式:對於每一個女生,計算排在他前面的男生數,然後把它全部加起來就是答案。 ```C for (i = 0, ans = 0 ; i < n ;i++) { if (a[i]==0) { cnt = num of 1 before a[i]; ans += cnt; } } ``` 效率取決於如何計算cnt。如每次拉一個迴圈來重算,時間會跑到 O(n^2^),如果利用類似前綴和 (prefix-sum)的概念,只需要線性時間。 ```C for (i = 0, cnt = 0, ans = 0 ; i <n ;i++) { if (a[i] == 0) ans += cnt; else cnt++; } ``` 接下來看分治思考模式。如果我們把序列在 i 處分成前後兩段 a[0, i - 1] 與 a[i, n],任何一個要找的 (1, 0) 數對只可能有三個可能:都在左邊、都在右邊、或是一左一右。所以我們可以左右分別遞迴求,對於一左一右的情形,我們若知道左邊有 x 個 1 以及右邊有 y 個 0,那答案就有 xy 個。遞迴終止條件是什麼呢?剩下一個就不必找了。 ```C int dc(int left, int right) { // 範圍=[ left,right) 慣用左閉右開區間 if (right - left < 2) return 0; int mid = (left + right) / 2; // 均勻分割 int w = dc(left, mid) + dc(mid, right); 計算x = 左邊幾個 1, y = 右邊幾個 0 return w + x * y; } ``` 時間複雜度呢?假設把範圍內的資料重新看一遍去計算 0 與 1 的數量,那需要線性時間,整個程序的時間變成 T(n) = 2T(n/2) + O(n),結果是O(nlogn),不好。比迴圈的方法差,原因是因為我們計算 0/1 的數量時重複計算。我們讓遞迴也回傳 0 與 1 的個數,效率就會改善了,用 python改寫: ```python def dc(left, right): if right - left == 1: if ar[left]==0: return 0, 1, 0 # 逆序數,0的數量,1的數量 return 0, 0, 1 mid = (left + right) // 2 #整數除法 w1, y1, x1 = dc(left,mid) w2, y2, x2 = dc(mid,right) return w1 + w2 + x1 * y2, y1 + y2, x1 + x2 ``` 時間效率是 T(n) = 2T(n/2) + O(1),所以結果是 $O(n)$。 如果分治可以做的迴圈也可以,那又何必學分治?第一,複雜的問題不容易用迴圈的思考找到答案;第二,有些問題迴圈很難做到跟分治一樣的效率。你可以不信我講的第一點,我們可以來看看第二點。上述男女對的問題其實是逆序數對問題的弱化版本:給一個數字序列,計算有多少逆序對,也就是 ``` | {(a[i], a[j]) | i < j 且 a[i] > a[j]} |。 ``` 迴圈的思考模式一樣去算每一個數字前方有多少大於它的數,直接做又搞到O(n^2),有沒有辦法像上面男女對問題一樣,紀錄一些簡單的資料來減少計算量呢?你或許想用二分搜,但問題是需要重排序,就我所知,除非搞個複雜的資料結構,否則沒有簡單的辦法可以來加速。那麼來看看分治。基本上的想法是從中間切割成兩段,各自遞迴計算逆序數並且各自排序好,排序的目的是讓合併時,對於每個左邊的元素可以笨笨地運用二分搜去算右邊有幾個小於它。 ```C++ LL sol(int le, int ri) { // 區間 = [le,ri) if (ri-le == 1) return 0; int mid = (ri + le) / 2; LL w = sol(le, mid) + sol(mid, ri); LL t = 0; for (int i = le; i < mid; i++) t += lower_bound(ar + mid, ar + ri, ar[i]) - (ar + mid); // C++內建二分搜 sort(ar + le, ar + ri); return w + t; } ``` 時間複雜度呢?即使我們笨笨地把兩個排好序的序列再整個重排,T(n) = 2T(n/2) + O(nlog(n)),結果是 O(nlog~2~(n)),十萬筆資料不需要一秒,比迴圈的方法好多了。為什麼說笨笨地二分蒐與笨笨地重新排序呢?對於兩個排好序的東西要合併其實可以用線性時間。那二分搜呢?沿路那麼多個二分搜其實可以維護兩個註標一路向右就好了。所以事實上不需要複雜的資料結構可以做到 O(nlogn),熟悉演算法的人其實看得出來,這個方法基本上就是很有名的 merge sort,跟 quick sort 一樣常拿來當作分治的範例。另外,如果merge sort的分割方式如果是 [left, right - 1] [right - 1, right],右邊只留一個,那就退化成 insertion sort 的尾遞迴。 註:計算遞迴的時間需要解遞迴函數,這是有點複雜的事情。好在大多數常見的有公式解。 Tail recursion 是遞迴的一種特殊形式,副程式只有在最後一個動作才呼叫自己。以演算法的角度來說,recursion tree 全部是一脈單傳,所以間複雜度是線性個該副程式的時間。不過遞迴是需要系統使用 stack 來儲存某些資料,於是還是會有 stack overflow 的問題。但是從編譯器的角度來說,因為最後一個動作才呼叫遞迴,所以很多 stack 資料是沒用的,所以他是可以被優化的。基本上,優化以後就不會有時間與空間效率的問題。 注意: Python 沒有 tail recursion 優化,而且 stack 深度不到 1000。C 要開編譯器開啟最佳化才會做 tail recursion 優化。 延伸閱讀: * [你所不知道的C語言:遞迴呼叫篇](https://hackmd.io/s/rJ8BOjGGl) * [On Recursion, Continuations and Trampolines](https://eli.thegreenplace.net/2017/on-recursion-continuations-and-trampolines/) ###### tags: `cs:app`, `csapp`