再帰

背景・歴史

数学における「漸化式」のように、ある値を、同じ種類のより小さな値を使って定義するという考え方は、古くから存在していました。例えば、階乗（5の階乗は5×4の階乗、というように定義できる）や、フィボナッチ数列は、この考え方の代表例です。プログラミング言語が発展する中で、こうした数学的な定義をそのままプログラムとして表現できるように、関数が自分自身を呼び出す「再帰」という書き方が、関数型プログラミング言語を中心に取り入れられ、現在では多くのプログラミング言語で使える基本的な技法になっています。

なぜこの考え方が使われるようになったのか

木の枝分かれのように、同じ構造が何段階にもわたって繰り返されるデータや問題を扱う場合、繰り返し処理（ループ）だけで表現しようとすると、プログラムが複雑になりがちです。再帰を使うと、「大きな問題を、同じ形をしたより小さな問題に分解し、それを解決すれば元の問題も解決する」という考え方を、そのままプログラムの構造として表現できます。これにより、複雑な問題を、驚くほどシンプルで見通しの良いプログラムとして記述できる場合があります。

もう少し詳しく見てみる

再帰を使ったプログラムには、次の2つの要素が欠かせません。

• 基本部分（終了条件）：それ以上分解する必要がない、最も単純な場合の答えを直接返す部分。
• 再帰部分：問題をより小さな同じ形の問題に分解し、その小さな問題を解くために自分自身を呼び出す部分。

終了条件を書き忘れると、関数が自分自身を呼び出し続けて処理が終わらなくなってしまうため、再帰を使う際には、必ず「小さくなった問題がいつかは基本部分にたどり着く」ように設計する必要があります。フォルダの中にフォルダが入れ子になっている構造をすべて調べる処理や、階乗の計算などは、再帰を使うと分かりやすく表現できる代表的な例です。

関連して知っておきたいこと

再帰は、関数が自分自身を呼び出すという特殊な性質を利用した技法です。再帰を使わなくても繰り返し処理で同じ結果を得られる場合も多くありますが、問題の構造によっては、再帰を使うことでアルゴリズムをより自然に、簡潔に表現できます。