我的DSA日記 — 1

遞迴(Recursion) & 堆疊(Stack)

Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation! 
-by Leigh Caldwell on Stackoverflow

遞迴和迴圈是不同的!

迴圈是大多數人比較熟悉的,畢竟在剛開始學寫程式都會學到while-loop與for-loop的概念,所以每當遇到要重複執行程式的時候,都會先想到迴圈。但事實上,迴圈是比較沒那麼直觀的。看見書上的實際例子:假設要找一把能夠打開門的鑰匙,這個鑰匙就放在A箱子內,而A箱子內還有B、C、D...等等的中箱子,每個中箱子內又都有小箱子,試問要用什麼樣的演算法來找到鑰匙?

一、迴圈
把箱子堆在一區→拿起離你最近的一個箱子→裡頭有鑰匙就結束,裡頭若沒有鑰匙則把裏面的所有箱子拿出來,並且把這些箱子擺到堆放箱子的區域→繼續從箱子區拿起離你最近的一個箱子

二、遞迴
拿起一個箱子→裡頭若是鑰匙就結束,否則檢查裏面的第一個箱子直到檢查完,才換另一個箱子

遞迴是比較直接的,我們在A箱內看到B、C、D,通常就事先檢查B,直到B內所有都被檢查過後,才換C。用文字說不明白,到底什麼是遞迴的定義?就是指會呼叫自身的函數。


遞迴的限制條件

由於遞迴會不斷呼叫自身的函數,所以當條件沒有設定好時,就會無限循環下去。因此每當要設計一個遞迴時,都需將問題拆成兩個部份:

  1. 基本情況(Base case):在基本情況時,函數不會呼叫自身,所以遞迴就能在這裡被擋住,無法無限循環。
  2. 遞迴情況(Recursive case):持續呼叫自身,所以遞迴會繼續進行下去。

以上面的找鑰匙為例,”elif 這個東西是鑰匙” 就是Base case,而其他部份就是Recursive case。


堆疊(Stack)

堆疊是一種資料結構,可以用來理解遞迴,可以視作一個概念。首先,只要有呼叫函數,就會呼叫堆疊。每當呼叫函數時,記憶體都會規劃出一個空間給該函數使用,裏面儲存了函數名字、參數、引數,而當函數執行完,這個空間就會被移除。而當函數內又有呼叫一個函數時,第二個函數的記憶體空間就會被堆疊在第一個函數之上,直到第二個函數執行結束,才會從第一個函數上方被移走,接著繼續把第一個函數執行完。

那跟遞迴有什麼關係?遞迴就是在函數內不斷地呼叫自身,因此就能看到記憶體被一直往上疊,直到Base case發生,這些函數慢慢執行完,才會漸漸從記憶體內被移走。

因此,當寫了一個不會結束的遞迴函數,這個遞迴就會不斷的呼叫同一個函數,他呼叫的每一個函數也都會佔有一個空間,一直下去直到記憶體空間被函數完全塞滿,然後呢?然後就當機了。這種呼叫堆疊直到記憶體被塞滿,就稱做堆疊溢位(Stack Overflow)。原來程式發問平台的命名是這樣來的啊…

回到第一段,Leigh Caldwell說遞迴有助於提升程式設計者的效益,這句話的意思是,寫遞迴對我們人類來說是比較直觀的、好設計的,但對電腦就不是那麼友善,因為遞迴有可能需要大量的空間來儲存暫時的呼叫堆疊,所以使用遞迴是沒辦法在效能上面給予什麼幫助的。若要避免這樣的情況產生,要不就改用迴圈來設計程式碼,要不就使用尾端遞迴(Tail Recursion)。←這要再查查!

Like what you read? Give Chia Hung Lin a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.