電腦科學 ^ IT人生 ^ 公益課程

#17 客戶說程式碼不能有 recursive function,該怎麼辦 ?

不知大家有沒有被客戶這樣要求過,寫程式一律不準出現 recursive 的寫法.這也是十年前左右的故事了,並不是我個人遇到的狀況,是我朋友們遇過的情況.當時對這樣的要求沒太多的頭緒,不過心裡還是把這問題放著,也許有一天我會知道為什麼.

後來,有一次因為一個考試,突然讓我想到這個問題可能的答案,從技術角度來看的話,我想這應該是客戶的顧慮.情況是這樣的,在作業系統中,每個工作被執行的單位是 Process.一個作業系統裡會有許多的 Process 在執行,分別負責不同的功能,例如,有 Process 是專門負責處理 DNS 封包,有 Process 專門負責與印表機的通訊.所以,我們若自己寫一個程式在作業系統裡執行,這個程式也將是一個 Process,作業系統也就會負責他所需要做的工作內容.

在每個 Process 裡都會有一個獨立的記憶體空間用來儲存該 Process 需要的變數與資訊,其中有一項資訊叫 call stack,簡單的說是你的程式某個 function 呼叫了某個 function,然後再呼叫其他的 function,一直呼叫下去到作業系統的核心.因為這個記憶體空間的大小是有一個固定的量,所以當呼叫 function 一直無窮盡的進去下去的話,就很容易造成這個記憶體空間不夠用了,而形成了 call stack overflow 的情況.一旦這情況發生了,該 Process 就會被迫中止.

如果以作業系統的角度來想,程式裡不包含 recursive 寫法是很重要的.所以,一般的習慣都會採用 iterative 的寫法來取代 recursive 的寫法.在前面的 Binary search 文章裡,我們有介紹到 Binary search 的 recursive 寫法與 iterative 寫法.不同的情況會用到不同的寫法技巧,以 Binary search 來說,就是用兩個額外的 index 來做,如果是 Tree traversal 的話,通常是用 Stack 和 List 來把 recursive 寫法改成 iterative 寫法.

未來遇到適當的內容時,再來說明不同的 recusrive 寫法是如何改成 iterative 寫法.

Share:

0 意見:

張貼留言