岩通ソフトシステム株式会社はソフトウェア開発からサービスまでをトータルで提供するソリューションプロバイダです。

　以前のコラムの算法（アルゴリズム）とは少し異なりますが、再帰呼び出しについて、今回は記述します。再帰呼び出しは、一回分だけ自分で処理して、あとは自分のクローンを呼び出して処理してもらうという、ある意味手抜きのテクニックでもあると考えています。　　　　　

再帰呼び出しとは

　プログラミングを始めた人たちは、再帰呼び出し（recursive call）と聞くと何を思い浮かべるのでしょうか？ 再帰呼び出しですから、挫折などからの再起というわけではなくて、簡単に言うと自分自身である関数や手続きを自分が呼び出すことを言います。

なぜ必要？

　ではなぜ、そのようなことが必要になるのでしょうか？

　良く例にあるのは、階乗を解くプログラムで、一回呼び出される毎に掛け算を一回行い、階乗回自分を呼び出して答えを求めるものですが、階乗を求めるだけであれば、再帰呼び出しではなく、単純にループをすれば良いようにも思えますので、これはあくまでも説明のためということだと思います。

　以前のコラムで扱った深さ優先検索では、再帰呼び出しを使っているのですが、これだとどうでしょうか？ もちろんループを使って処理することもできますが、自ノードから出ているエッジをすべて処理するのが自分の役目で、エッジの先は再帰的に自分を呼び出してやってもらうと考えると、設計上もプログラミング上もかなりすっきりします。また、深さ優先検索のようにバックトラックとまでは行かないまでも、今まで来た道を戻るような処理が必要な場合には、場合にもよるとは思いますが、ただリターンするだけで一つ戻ることが簡単に実装できると思います。

注意する点は？

　注意しなければならないのは、再帰呼び出しでは一回呼び出す毎にスタックなどの資源を消費していきますから資源の余裕と呼び出し回数のバランスを取る必要があります。また、10÷3のように再帰呼び出しをしても収束しない問題に再帰呼び出しを使用する場合には、どこかで処理を打ち切るなどの対策が必要です。
　また、再帰呼び出しのもう一つの注意点ですが、自分自身を呼び出すのが、自分自身が行う処理の前なのか後なのかは十分考慮する必要があります。つまり、自分が呼び出された時に、呼び出し元の処理が終了していて自分の処理を行ってから自分自身をもう一回呼び出すのか、それとも自分が呼ばれた時には呼び出し元の処理は終了していなくて自分の処理を行う前に自分自身をもう一回呼び出すのかということです。また、深さ優先検索の処理のように自分自身の処理として再帰呼び出しをするという場合もありますので、どのパターンを使用するのが一番良いかを考える必要があります。

再帰呼び出しの技術要件

　最後に、注意点というよりも再帰呼び出しが使用できる条件ですが、再帰呼び出しされる関数や手続きは再入可能（リエントラント：Reentrant）である必要があります。リエントラントにするためには、プログラムの言語やコンパイラを含む処理系とプログラミング方法（データの扱い方など）の両方がリエントラントに対応する必要があります。
　再入可能については、説明し出すと長くなってしまうため、別の機会に譲ることにします。

---