再帰関数とは?

早速ですが、次のような問題を考えてみましょう。「ソウサ 4」の結果はいくつになるでしょうか。

ソウサ x：

• x=1 のとき、ソウサ x の結果は 1 である。
• x ≥ 2 のとき、ソウサ x の結果は「ソウサ x-1 の結果に x を足した値」である。

答えは下図の通り 1+2+3+4=10 になります。

さて、この例では答えを求めるために「ソウサの結果」を呼び出しており、このように自分自身を引用することを「再帰的定義」と言います。また、プログラミングにおいて自分自身を呼び出す関数を「再帰関数」と言います。再帰関数は、複雑なアルゴリズムを簡潔に実装するときに便利なツールである一方、初学者にとっては最初の壁になりがちです。そこで今回は、3 つの例を用いてわかりやすく解説していきたいと思います。