遞迴¶

Da-Wei Chiang¶

大綱¶

  • 遞迴簡述
  • 遞迴練習
  • 用堆疊看遞迴
  • 進階遞迴問題
    • 河內塔問題

遞迴簡述¶

  • 遞迴在程式開發中是一個非常實用的技巧. 其實這樣的技巧說穿了就是堆疊.
  • 遞迴的概念
    • 函數自己呼叫自己. 呼叫自己在程式的意義上相當於將問題拆解為子問題再進行解決
    • 終止遞迴函數的呼叫是設定終止條件.當終止條件成立即返回呼叫函數的地方
  • 簡單的遞迴問題
    • 階層
    • 費波那契數列
In [ ]:
## 遞迴 - 範例 階乘(以往作法)
def fact(num):
    fact_sum = 1
    for i in range(1, num+1):
        fact_sum*=i
    return fact_sum

num = int(input("input number:"))
fact_num = fact(num)
print("%s! = %s" %(num, fact_num))
In [3]:
## 遞迴 - 範例 階乘(遞迴作法)

def fact(num):
    if num == 0:
        return 1
    elif num == 1:
        return 1
    else:
        return num*fact(num-1)
    
num = int(input("input number:"))
fact_num = fact(num)

print("%s! = %s" %(num, fact_num))

input number:4
24

圖例 - 用堆疊看遞迴（階層為例）¶

圖例 - 用堆疊看遞迴（階層為例）¶

練習¶

  • 使用遞迴撰寫費波那契數列
    • 每一項是前兩項得和
      n0 = 0
  n1 = 1
  n2 = 1
  n3 = 2
  n4 = 3
  ...
    • 讓使用者輸入一個數, 輸出費波那契數列結果

進階遞迴問題¶

  • 河內塔問題
    • 河內塔遊戲

河內塔問題¶

  • 將圓盤從A木樁移動到C木樁
  • 移動時必須符合下述規則
    • 一次只能移動一個圓盤
    • 每次移動僅能移動最上面的圓盤
    • 必須保持小圓盤在大圓盤之上
  • A木樁稱為來源木樁、B木樁稱為輔助木樁、C木樁稱為目的木樁
  • 假設圓盤有n個. 完成河內塔問題的最佳移動次數為$2^n-1$.

圖例 - 河內塔問題¶

  • 以n = 3為例

圖例 - 河內塔問題¶

  • Step 1:

圖例 - 河內塔問題¶

  • Step 2:

圖例 - 河內塔問題¶

  • Step 3:

圖例 - 河內塔問題¶

  • Step 4:

圖例 - 河內塔問題¶

  • Step 5:

圖例 - 河內塔問題¶

  • Step 6:

圖例 - 河內塔問題¶

  • Step 7:
    • 整體移動次數$2^3-1=7$

練習¶

  • 請讓使用者輸入一個數(圓盤數)
  • 輸出圓盤從A木樁到C木樁的步驟

迷宮回溯演算法¶

  • 早期在現行的深度學習技術還不成熟時, 回溯演算法常被拿來設計電腦五子棋、跳棋...等遊戲
  • 回溯演算法
    • 是一種try and error的方法.
    • 其實作部分與堆疊有關, 我們將以走迷宮來介紹其演算法

迷宮問題¶

  • 請想想看, 要怎麼從入口(紅色區塊)走到出口(黃色區塊)

迷宮問題解法¶

  • Step1: 從迷宮起點開始
  • Step2: 依序進行上、下、左、右的行走
  • Step3: 若上下左右有可以走的, 並且無重複走過. 則往該方向走

迷宮問題圖例¶

迷宮問題圖例¶

迷宮問題圖例¶

程式的角度看迷宮問題¶

練習 - 解迷宮問題¶

  • 有個地圖如下(1為牆壁0為走道)
  • 入口座標為(4, 1). 出口座標為(1, 4)
  • 請將走過的地區數字改為2, 若無路可走導致回溯可用3表示
  • 使用pprint輸出地圖結果(pprint為換行輸出結果函數)
road_map = 
[[1, 1, 1, 1, 1, 1],
 [1, 0, 1, 1, 0, 1],
 [1, 0, 0, 0, 0, 1],
 [1, 0, 1, 0, 1, 1],
 [1, 0, 1, 0, 1, 1],
 [1, 1, 1, 1, 1, 1]]
 
from pprint import pprint
    
pprint(road_map)