[演算法]遞迴演算法 (Recursion)

將問題分解成基本情況(Base Case)、遞迴情況(Recursive Case)。這就是遞迴演算法的核心概念,透過此演算法,可以讓你有明確的方法來解決問題。

什麼是遞迴演算法?

遞迴 指的是一個 函數,重覆呼叫自己本身 函數

會將問題拆解成基本情況(Base Case)與遞迴情況(Recursive Case)。基本情況就是解決問題了,遞迴情況就是尚未解決問題,需再透過同樣的方式繼續去解決問題。

Base Case(基本情況) 與 Recursive Case(遞迴情況)

舉個例子:假設有很多個盒子,而每個盒子裡都可能還有盒子,而目標是要找到只有一個盒子裡面有一把鑰匙。

先試試不是遞迴的方式:思維步驟如下:

1、把每個盒子堆在一起,準備檢查

2、拿起一個盒子,仔細檢查

3、如果裡面是盒子,將盒子加入堆起的盒子,稍後再檢查

4、如果找到鑰匙,成功!

5、從上述第2點開始重覆再次尋找

 

遞迴解法:思維步驟如下:

1、檢查盒子

2、如果裡面是盒子,回到上述步驟 1

3、如果找到鑰匙,成功!

這個遞迴解法,轉換成虛擬碼(Pseudocode)的話(虛擬碼就是比較接近人在看的程式),如下:

function look_for_key(box){
  for item in box:
    if item.is_a_box(): // 這就是遞迴情況,需要再次呼叫自己函式
      look_for_key(item) // 這就是遞迴的方式,呼叫自己函式本身。
    else if item.is_a_key(): // 這就是基本情況,解決問題了。
      print "找到鑰匙!"
}

 

呼叫堆疊(Call Stack)

Call Stack 是一般程式設計的重要概念,也是遞迴函數必瞭解的概念。

可以想像使用便利貼來做代辦事項,假設一張便利貼就是一個代辦事項,能做的動做就是2個:插入(Push) 和 移除並讀取(Pop)。有一個代辦事項,就放在前一個代辦事項便利貼的上方(Push),而每次要移除一個代辦事項,也是要從最上方開始移除並讀取(Pop),不斷地 Push 或 Pop。這樣的資料結構稱為堆疊(Stack)

您可在此處留言

搶先留言!

avatar
  Subscribe  
Notify of