道理我都懂，但 Stack 到底為什麼會 Overflow
身為工程師，Stack Overflow 這網站大家應該都是熟到不能再熟。如果沒有他幫忙解決各種莫名其妙的錯誤訊息，可能連設定個開發環境都要搞半天，更不用說要開發了，產出直接降低好幾倍，不如直接放工程師下班算了。
但今天要談的不是那個 Stack Overflow，而是要講程式在使用記憶體時，因為 call stack 堆太高了不小心把記憶體用完，所產生的 overflow。
先來看看以下這個用 JS 寫成的 sum(n)，他做的事情很簡單，就只是用遞迴來計算從 1 到 n 的總和，譬如說 sum(3) = 1 + 2 + 3 = 6。
這寫法很爛我知道，不過為了示範請大家包容一下XD，實際跑跑看 sum(10) 跟 sum(10000) 也都有得到正確的結果。
但跑 sum(20000) 時就不是這樣了，因為程式寫太爛加上 20000 這數字太大，直接就原地炸開噴出 RangeError: Maximum call stack size exceeded，這就是所謂的 Stack Overflow。
Stack in memory layout
看過 Stack Overflow 之後，我們來講解一下他的成因，首先看看到底什麼是 Stack。每個 Process 在啟動時，系統都會分配一塊記憶體給他使用，以最常見的 memory layout 來說，Process 內的 memory layout 大概會長這樣，由低位到高位主要分成 Text、Data、Heap、Stack 幾個區塊。
最下面的 Text 區塊放的是要給 CPU 跑的 executable instruction，一般來說你的程式碼越多，這部分就會越肥；而 Data 區塊放的就是 process 內的全域、靜態變數，有設定初始值的就會被放在 Initialized，沒有的話就是在 Uninitialized，程式啟動時會把他們的值清空成 0。
Text 跟 Data 這兩個區塊基本上是固定大小，因為你寫的程式一旦編譯好，程式碼跟全域變數的數量就會固定下來，不太會動態增長。但 Heap 跟 Stack 就不一樣了，當程式有用到動態記憶體配置像是 C 語言的 malloc/free、Rust 的 Box，那些空間就會被分配在 Heap 裡面。
而最上面的 Stack 也就是這篇的重點，則是放 call function 時會用到的一些東西，像是傳進來的參數、自己宣告的變數等等，每個 function 啟動時會有一個 stack frame 被創造出來，結束時再馬上釋放掉。
Deep Recursive Function
那遞迴是怎麼讓 Stack 爆掉的呢？以我們的例子來說，當我們呼叫 sum(3) 時，他內部會先呼叫 sum(2)，而 sum(2) 又再呼叫 sum(1)，因此整個 Stack 裡面會有多個 stack frame 依序疊起來，只有當最上層的 sum(1) 執行結束了之後，才有辦法繼續執行下面的 sum(2) 跟 sum(3)。
雖然 stack 可以動態增長，但他的大小也是有極限的，作業系統總不可能為了跑你的程式而把整台電腦的 memory 都給你。
因此當你呼叫 sum(20000) 導致遞迴太深時，等待執行的 function 有太多，但 stack 已經裝不下更多 frame，就會產生 overflow 的錯誤，仔細看一下是不是跟 Stack Overflow 的 logo 有 87% 像呢XD
雖然一般來說都是遞迴沒寫好才會導致 Stack Overflow，但其實 Stack Overflow 並不一定是遞迴造成的，只要你的 call stack 夠深（真的要非常非常深），那就可能會有這個。
How to fix Stack Overflow
若真的不幸遇到 Stack Overflow 要怎麼解決呢？第一步就是先檢查遞迴的終止條件。像這邊如果沒有在 n == 1 時 return 1，那就算只是跑個 sum(3) 也會炸掉。
如果檢查後都沒有寫錯，但參數太大時還是會爆掉，那就是得想辦法把遞迴攤平成迴圈了，像 sum 很明顯就可以用一個迴圈或是公式解把它做完：
那如果像是 Merge Sort 這種比較難直覺攤平成 loop 的演算法呢？
通常這種被廣泛使用的演算法的 call stack 都不會太深，因為這類演算法為了加速都會大量使用 Divide and Conquer 的技巧，像 Merge Sort 就會不斷把 array 切成兩半。因此除非你的資料量有超過 2¹⁰⁰⁰⁰ ≈ 10³⁰¹⁰ 筆，否則 call stack 再深也不可能超過電腦的限制。
所以如果你自己寫的 Merge Sort 不知道為啥跑起來會 Stack Overflow，不用懷疑，百分之百是你寫錯了XD
Summary
下次再有人問你「工程師賴以為生的 Stack Overflow 到底是什麼意思啊？」，相信大家應該都可以輕鬆講出來了。
因為這篇是用 Node.js 來展示 Stack Overflow 的錯誤，所以實際的 memory layout 可能跟上面畫的有些許不同（每個語言都有自己一套管理記憶體的方式），但概念基本上都是相通的。
今天講完 Stack Overflow，下次有空時應該會再延續這個主題，寫一篇關於尾遞迴最佳化（Tail Call Optimization）的文章，大家敬請期待啦～
