再帰関数とは

アルゴリズムを勉強していて、再帰関数でつまづいたので備忘録です。

再帰関数とは

関数の中で、自分自身を呼び出す関数のこと。

サンプルコードを示しましょう!

サンプルコード

countdown関数が再帰的に呼び出されています。

ここで立ち止まって欲しいのですが、上記のコードは致命的なミスを犯しています。

無限ループになってしまっています。

無限ループを避けるためには、以下の2点を考慮してコードを書く必要があります。

  • 基本ケース
  • 再帰ケース

以上のことを踏まえてコードを書き直します。

これで、再帰関数を定義することができました。

コールスタック

再帰関数を理解する上で、コールスタックの理解は必須です。

関数が呼び出されるたびに、PCはその呼び出しに対する変数の値をスタック(メモリ)に保存します。

上記のコードでは、以下の画像のように変数がスタックに保存されていきます。

詳細に言うと、その関数内での処理が完了するまでスタックに保存され、完了するとポップされます。(メモリから消える)

肝は、

関数から別の関数を呼び出すと、呼び出している側の関数は部分的に完了した状態で中断されます。

上の例で言うと、

greet2関数が完了した時点で、処理はgreet関数に戻り、処理を中断したところから再開します。

上記で説明したよう、複数の関数の変数を保存するスタックのことをコールスタックと呼ぶらしいです。

 

再帰関数におけるコールスタック

数字の階乗を計算する再帰関数を書いていきます。

下図を参考にすると、それぞれの関数でreturnされる毎に上からポップされる。

変数の値がスタックに保存されるのが肝です。

まとめ

コールスタックの部分が難しかったのですが、図を書くと理解しやすかったです。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA