KATOエンジニヤリング開発日誌

「アウトプット無きエンジニアにインプットもチャンスも無い」の精神で書いています

「なっとくアルゴリズム」を読んだ - 再帰 -

前回に続いて「なっとくアルゴリズム」を読んで理解したことのまとめです。

www.kato-eng.info

再帰

再帰を利用したプログラムはwhileループを使って代用することができる。但し、再帰を使うことによるパフォーマンス上のメリットは無く、むしろループの方がパフォーマンスが良い場合もある。

再帰が使われるのはそれによるソリューションがより明確になる場合に使うと良い。

基本ケースと再帰ケース

再帰関数は自身を呼び出すため、無限ループに陥ってしまいがち。なので再帰関数を書くときは再帰をいつ終了するのかを指定してあげる必要がある。このため、すべての再帰は「基本ケース」と「再帰ケース」の2つの部分で構成されることになる。

  • 基本ケース
    • 関数が自身を呼び出さないので無限ループにはならない
  • 再帰ケース
    • 関数が自身を呼び出す部分

引数として数値を与えられるとカウントダウンを始める再帰関数は下記のようになる。

# Python
def countdown(i):
    print(i)
    # 基本ケース
    if i <= 0:
        return
    # 再帰ケース
    else:
        countdown(i - 1)

スタック

再帰を使うときにはコールスタックという概念について理解しておくことが重要である。

上記の「countdown」再帰関数に引数「3」を与えると下記のようになる。

f:id:masayuki_kato:20170930105522j:plain

空のスタックに「countdown(3)」プッシュされる。

f:id:masayuki_kato:20170930113306j:plain

スタックに積まれている「countdown(3)」が再帰ケースを呼び出し「countdown(2)」が新たにスタックにプッシュされる。

f:id:masayuki_kato:20170930115138j:plain

同様にスタックに積まれている「countdown(2)」が再帰ケースを呼び出し「countdown(1)」が新たにスタックにプッシュされる。

f:id:masayuki_kato:20170930115609j:plain

同様にスタックに積まれている「countdown(1)」が再帰ケースを呼び出し「countdown(0)」が新たにスタックにプッシュされる。

f:id:masayuki_kato:20170930115738j:plain

「countdown(0)」は基本ケースを呼び出すので「countdown(0)」の関数が終了する。と同時にスタックに積まれている「countdown(0)」がポップされる。

f:id:masayuki_kato:20170930115953j:plain

処理がスタックの一番上に積まれている「countdown(1)」に移る。「countdown(1)」は再帰関数「countdown(0)」を呼び出した後は特に処理が無いので終了する。と同時にスタックに積まれている「countdown(1)」がポップされる。

「countdown(1)」がポップされるとスタックの一番上に積まれている「countdown(2)」処理が移る。これらの処理が続いて最終的には全ての再帰関数がポップされる。

再帰関数の例

階乗を再帰関数で定義すると下記のようになる。

# Python
def factorial(x):
    if x == 1:
        return x
    else:
        return x * factorial(x - 1)

まとめ

再帰とは関数が自身を呼び出すことであり、すべての再帰関数は「基本ケース」と「再帰ケース」で構成される。

再帰を実行するとコールスタックに関数が配置されるが、スタックに積まれる関数が非常に多くなることがあり、その場合は多くのメモリを消費してしまうことになるので注意が必要。