再帰関数

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

再帰の仕組み

• コンピューターはスタックを使って関数の呼び出し状況を管理
  • コールスタック

再帰の仕組み

• 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を返す

動的計画法

• 最適化手法
• 主に再帰処理に適用される
• 再帰アルゴリズムの計算量を削減できる
• 使用される場面：
  • 小さなサブ問題に分割できる問題
  • サブ問題が重複して発生する場合
• サブ問題の解答が保存され、再利用できる
  • メモ化

練習しましょう！

Pythonで学ぶデータ構造とアルゴリズム