再帰関数は、プログラミングを学び始めたときに壁になりやすい処理の一つ。
実際、筆者も学びはじめたときはその概念の理解に苦労しました。
再帰関数が難しいと感じる理由には、以下のようなものがあると思います。
- 関数自身を実行するという処理が直感的にイメージしづらい
- 利用する場面が分からない
本稿では、そんな再帰関数を処理イメージから理解し、利用できる場面などを交えて説明していきます！ 読了目安時間は10分を目指しています。
再帰関数のしくみ
再帰関数とは関数内で関数自身を呼び出す関数のことです。
また、再帰関数に限らず自分自身を呼び出すような処理を再帰的(recursive)であるといい、再帰的な処理実行を再帰呼び出しと言ったりもします。
再起部
後述する基底部に至るまで繰り返し実行される処理。
画像は変数nの階乗を求めるfactorial関数で、再帰部では変数nにfactorial(n – 1)の結果を乗じています。
関数自身を関数呼び出しの中で繰り返し実行し、その実行結果にその関数自身の計算処理をちょい足ししたものを関数の結果として返します。
基底部
再起処理の終了条件で呼び出される処理。
再帰関数は繰り返し自分自身を呼び出す関数なので、関数の構造が再帰部分だけの場合、再帰呼び出しが無限ループ（無限再帰）になるリスクがあります。
そのため、「何が何でも絶対にここで処理を食い止める！」ためのかんたんな条件の呼び出しを関数定義の中に含めておきます。
関数factorialを例にとると、再帰部分の呼び出しごとに引数nが「5→4→3…」と1ずつ減っていくので、最終的にn=1という条件を通ることは想像しやすいと思います。
再帰関数の実行結果と評価
スタックフレーム
プログラムでは、関数を呼び出す際に関数の引数やローカル変数、関数の戻り先情報などの環境を保持するためのメモリ領域が確保されます。
このように、関数呼び出し時の環境を保持するための領域を「スタック領域」、それぞれの関数呼び出しごとに作られる環境のことを「スタックフレーム」と呼びます。
評価
関数を順番にスタックに追加していくと、最終的に再起呼び出し処理の基底部に到達します。
基底部に到達すると、作成されたスタックフレームを最後に追加されたものから順番に取り出していき、各関数呼び出しの環境を再現しながら、計算結果を評価します。
評価結果は、スタックフレームに保持された関数の戻り先情報を元に呼び出し元に返却され、呼び出し元で最終的な計算結果(= 120)が得られます。
再帰関数の利用場面とメリット
再帰関数を有効に使うことができる利用場面としては、以下のようなパターンが考えられます。
- 組み合わせ列挙
- 繰返し処理（ループ処理）
- ツリー構造の処理
組み合わせ列挙
組み合わせの列挙は、プログラミングコンテストでの頻出の問題です。
各アルゴリズムの詳細な説明については割愛しますが、具体的には以下のようなアルゴリズムで再帰関数を有効活用することができます。
- 動的計画法
- 全探索
繰返し処理
繰返し処理は一般的に各言語の持つループ文(forなど)を使った記法で記述すことができますね。
プログラミングにおいて基本的な処理のひとつなので、初心者でも扱いやすい処理のはずです。
一方で、for文などを使ったループ記法は人間の数学的思考方法に対して直感的ではないという欠点もあります。
例えば、上の画像で取り上げた階乗の計算(factorial)は、ループで記述することもできますが、再帰的に定義する方がより直感的に記述することができます。
また、再帰関数の定義は数学の漸化式と対応するため記述がシンプルで可読性が高くなるというメリットがあります。
木構造
フォルダツリーを上から順番に探索するなどの処理を記述する場合は、そのフォルダの深さがどれくらいになるか処理の実行時点ではわからないことも多いため、ループでは処理が難しくなることがあります。
そのような場合は、木構造の子要素がない場合を基底部とした再帰関数として定義することで、処理を直感的かつシンプルに記述することが可能です。
再帰関数のデメリット
繰り返し処理や組み合わせ列挙などで便利に使える再帰関数ですが、いくつかのリスクを抱えています。
- 処理の終了条件(基底部)が間違っていると、再帰呼び出しが終わらなくなる。
（無限再帰） - 再帰呼び出しの回数が多すぎると、スタック領域のメモリが足りなくなる
（スタックオーバーフロー）
再帰関数を利用する際には、無限再帰やスタックオーバーフローのリスクがあることを加味したうえで問題のない作りにする必要があります。
また、このようなリスクを回避する方法として、末尾再起最適化という方法があります。
まとめ
- 再帰関数とは、自分自身を呼び出す関数
- 再帰関数を使うことで、直感的でより明確な関数定義になる可能性がある
- 使う時は、無限再帰になる可能性やスタックオーバーフローに注意！
再帰関数は、関数型言語を勉強したりすると必ずと言っていいほどお世話になる概念です。
正しく使えるようになることで、プログラムの可読性を向上させたり、より複雑なアルゴリズムを作れるようになるなどのメリットもありますので、ぜひ身につけてエンジニアとしてワンランクアップを目指しましょう！
コメント