再帰とは？仕組み・例・ベースケースをわかりやすく解説

数学における再帰とは、関数・数列・手続きを、同じ考え方のより小さい場合を使って定義することです。再帰的な定義が成り立つのは、ベースケースと、各場合をそのベースケースへ近づける規則の両方があるときだけです。

要点だけを言えば、再帰は「より小さい場合へ進む規則」が正しい停止点にたどり着かなくなった瞬間に、役に立たなくなります。

数学での再帰の意味

再帰的な定義では、すべての場合を個別に並べません。代わりに、出発点と、より小さい場合からより大きい場合を作る規則を与えます。

これは直接公式とは異なります。直接公式は、入力から1つの式で答えを与えます。再帰的な定義は、すでにわかっている場合に到達するまで、問題を段階的に小さくしていきます。

ベースケースは停止点です。これがないと、定義はより小さい場合を延々と参照し続け、いつまでも終わりません。

また、ベースケースは選んだ規則とも整合していなければなりません。再帰ステップが $n$ から $n-1$ へ減らす形なら、許される入力に対して、そのパターンで到達できるベースケースが必要です。

階乗は、再帰的定義の標準的な例です。整数 $n \ge 0$ に対して、階乗を次のように定義します。

0! = 1

そして、 $n \ge 1$ のとき、

n! = n(n-1)!

ここで、 $0! = 1$ がベースケースで、 $n! = n(n-1)!$ が再帰ステップです。

$4!$ を求めるには、ベースケースが現れるまで順に小さくしていきます。

4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!

ここでベースケース $0! = 1$ を使います。

4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24

これが再帰の全体的な流れです。より小さい場合へ減らし、ベースケースに到達し、その後で元の問題まで計算を戻していきます。

再帰は、より広い考え方です。漸化式は数列に対する再帰的な規則で、各項がそれ以前の項に依存します。

たとえば、フィボナッチ数列は各項が前の項から定まるので、漸化式で与えられます。階乗も再帰的ですが、通常は数列の漸化式というより、関数の再帰的定義として説明されます。

ベースケースがなければ、その定義は終わりません。

再帰ステップがベースケースへ近づいていないと、処理が永遠に続いたり、ある入力では未定義になったりします。

階乗の例では、規則 $n! = n(n-1)!$ は $n \ge 1$ のときに使います。この条件は重要です。これがないと、本来その定義を適用しない場面でも規則を使おうとしてしまいます。

再帰は、コードよりずっと前から数学に現れます。これは、関数・数列・集合を、より小さい場合を参照して定義する方法です。そして、そのような再帰的定義についての性質を証明するのに、数学的帰納法がよく使われます。

再帰は、問題が自然に「自分自身のより小さい版」に分かれるときに役立ちます。階乗、フィボナッチ型の数列、再帰的に定義された集合、多くのアルゴリズムで見ることができます。

特に、より小さい場合が元の問題と同じ構造を持つときに有効です。もし小さい場合が本当に同じ種類の問題でないなら、再帰はたいてい適切な道具ではありません。

次の2つを自分に問いかけてください。

どちらかの答えが「いいえ」なら、その定義は修正が必要です。

次のように数列を定義します。

a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2

このとき、 $a_2$ 、 $a_3$ 、 $a_4$ を求めてみましょう。新しい設定でベースケースと再帰ステップを見抜く練習として、手軽に取り組めます。

問題をアップロードすると、検証済みのステップバイステップ解答が数秒で届きます。