理解遞迴

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

定義

• 函式呼叫自身
• 幾乎所有用迴圈的情境
  • 皆可用遞迴取代
• 能解決初看很複雜的問題

範例－階乘

$n!$

範例－階乘

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120

範例－用遞迴求階乘

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)

• 會一直執行！

範例－找出基底情況

• 加入條件
  • 確保演算法不會無限執行
• 階乘的基底情況 -> $n=1$

def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120

遞迴如何運作

• 電腦用 stack 追蹤函式呼叫
  • 呼叫堆疊（call stack）

遞迴如何運作

• factorial(5) 開始
• 在 factorial(5) 結束前 -> factorial(4) 開始
• 在 factorial(4) 結束前 -> factorial(3) 開始

遞迴如何運作

• factorial(5) 開始
• 在 factorial(5) 結束前 -> factorial(4) 開始
• 在 factorial(4) 結束前 -> factorial(3) 開始
• 在 factorial(3) 結束前 -> factorial(2) 開始

遞迴如何運作

• factorial(5) 開始
• 在 factorial(5) 結束前 -> factorial(4) 開始
• 在 factorial(4) 結束前 -> factorial(3) 開始
• 在 factorial(3) 結束前 -> factorial(2) 開始
• 在 factorial(2) 結束前 -> factorial(1) 開始

遞迴如何運作

• factorial(5) 開始
• 在 factorial(5) 結束前 -> factorial(4) 開始
• 在 factorial(4) 結束前 -> factorial(3) 開始
• 在 factorial(3) 結束前 -> factorial(2) 開始
• 在 factorial(2) 結束前 -> factorial(1) 開始

遞迴如何運作

• factorial(1) 結束
  • 回傳 1
• factorial(2) 結束

遞迴如何運作

• factorial(1) 結束
  • 回傳 1
• factorial(2) 結束
  • 回傳 2

遞迴如何運作

• factorial(1) 結束
  • 回傳 1
• factorial(2) 結束
  • 回傳 2
• factorial(3) 結束
  • 回傳 6

遞迴如何運作

• factorial(1) 結束
  • 回傳 1
• factorial(2) 結束
  • 回傳 2
• factorial(3) 結束
  • 回傳 6
• factorial(4) 結束
  • 回傳 24

遞迴如何運作

• factorial(1) 結束
  • 回傳 1
• factorial(2) 結束
  • 回傳 2
• factorial(3) 結束
  • 回傳 6
• factorial(4) 結束
  • 回傳 24
• factorial(5) 結束
  • 回傳 120

遞迴如何運作

• factorial(1) 結束
  • 回傳 1
• factorial(2) 結束
  • 回傳 2
• factorial(3) 結束
  • 回傳 6
• factorial(4) 結束
  • 回傳 24
• factorial(5) 結束
  • 回傳 120

動態規劃

• 最佳化技術
• 主要用於遞迴
• 可降低遞迴演算法的複雜度
• 用於：
  • 可分解為較小子問題的任何問題
  • 子問題彼此重疊
• 儲存子問題解，避免重算
  • 記憶化（memoization）

一起來練習吧！

Data Structures and Algorithms in Python