再帰関数とメモ化と分割統治法

  • 再帰関数
    • GCD(m, n) - 2つの整数から最大公約数を求める
      • ベースケース
      • 可視化
  • 再帰関数とメモ化

  • 部分和問題(最適な部分集合を見つける) with 分割統治法

    • 再帰関数を使うことで問題を少問題に分割できる

再帰関数

  • ベースケース
  • 振る舞いの可視化

ユークリッドの互除法

2つの整数m, n(m ≧ n)において、以下の手順を繰り返すことで最大公約数を求めることができる。

  1. 入力を m, n (m ≧ n) とする。
  2. n = 0 なら、 mを出力してアルゴリズムを終了する。
  3. mをnで割った余りを新たに nとし更に 元のnを新たにm とし 2. に戻る。
fn gcd(m: u32, n: u32) -> u32 {
    return if n == 0 {
        m
    } else {
        gcd(n, m % n)
    }
}

ベースケースと処理の可視化

無限ループしないように、ベースケースを定め、returnする。

f:id:yossan2:20211205183926p:plain

再帰関数とメモ化

フィボナッチ数列

f:id:yossan2:20211205183909p:plain

部分和問題 with 分割統治法

f:id:yossan2:20211205183849p:plain

参考書籍

https://www.amazon.co.jp/問題解決力を鍛える!アルゴリズムとデータ構造-KS情報科学専門書-大槻兼資-ebook/dp/B08PV83L3N