再帰を理解する

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で学ぶデータ構造とアルゴリズム