本文へスキップ
BecomeCoder
ブログ一覧コース一覧

再帰とは？わかりやすく解説｜初心者向けに「自分を呼ぶ関数」を例で理解

#再帰#関数#初心者#独学#アルゴリズム

結論：再帰とは「自分自身を呼び出す関数」のこと。そして命なのは、呼び出しを止める条件＝ベースケースです。 ベースケースがあれば「同じ形の小さな問題」に分解して答えにたどり着け、なければ無限に呼び続けてエラー（スタックオーバーフロー）になります。この「呼ぶ」と「止まる」を、頭で追うより実際にコードを動かして目で確認するのが、理解への一番の近道です。

再帰とは？ ― 自分を呼ぶ関数のこと

関数（メソッド）は、ふつう「別の関数」を呼び出します。再帰は、その呼び出す相手が自分自身になっているだけです。それだけのことなのに難しく感じるのは、「自分の中で自分を使う」という形が最初は目で追いにくいからです。

考え方はシンプルです。大きな問題を、同じ形のひとまわり小さい問題に分解する。小さくしていけば、いつか「もう分解しなくていい一番小さいケース」に行き着きます。この一番小さいケースが**ベースケース（終了条件）**です。

そもそも「関数って何？」がまだあいまいなら、先に関数の基本から手を動かすのがおすすめです。Python 第18回「関数の定義」 や JavaScript 第18回「関数の定義」 を、ブラウザでそのまま実行しながら学べます（無料・登録不要・環境構築なし）。

いちばん簡単な例：階乗を再帰で書く

再帰の定番は「階乗」です。5!（5の階乗）は 5 × 4 × 3 × 2 × 1 = 120。これを「n の階乗は n × (n-1の階乗)」と言い換えると、そのまま再帰になります。

static int factorial(int n) {
    if (n <= 1) {
        return 1;                      // ベースケース：ここで止まる
    }
    return n * factorial(n - 1);       // 自分自身を呼ぶ（＝再帰）
}

この階乗の例は、そのままブラウザで動かせるレッスンになっています。渡す数字を変えて結果がどう変わるか、if (n <= 1) の行を消すと何が起きるかまで試せます。→ Java 第28回「再帰 ― メソッドが自分自身を呼び出す」（実行できます・無料）。

「for や while は分かるのに再帰は苦手」という人へ。再帰は「同じ処理を、少しずつ小さくしながら繰り返す」ループの親戚です。違うのは、繰り返しの回数を変数で数えるのではなく、引数を小さくしていって、ベースケースで止めるという点だけです。

つまずき①：ベースケースを忘れると無限再帰になる

再帰で初心者が最初にぶつかる壁が、ベースケースの書き忘れです。止める条件がないと、関数は自分を呼び続けて永遠に終わりません。実際には「永遠」ではなく、呼び出しの記録を積む領域（コールスタック）が溢れてエラーで止まります。これがいわゆる「スタックオーバーフロー」です。

言語によってエラー名が違うだけで、原因はすべて同じ「止まらない再帰」です。自分の使う言語の逆引きで、実際のメッセージと直し方を確認しておくと安心です。

多くの人がここで詰まりますが、対処はいつも同じです。「一番小さいケースはどこ？そこで確実に return しているか？」を確認すること。そして、自分を呼ぶときに引数がちゃんと小さくなっているか（n - 1 になっているか、n のままになっていないか）を見ることです。

つまずき②：頭で追おうとして混乱する

再帰は、紙の上で「呼んで、呼んで、戻って、戻って」を全部追おうとすると混乱します。おすすめは追わないこと。次の2点だけを信じます。

  1. ベースケースは正しい答えを返すか？
  2. 「1つ小さい問題の答え」が正しいと仮定したら、いまの答えは正しく組み立てられているか？

この2つがOKなら、あいだの膨大な呼び出しは自動的に正しくなります。これは数学的帰納法とまったく同じ考え方で、再帰が「わかった」と感じる瞬間はたいてい、この「1つ下は信じてよい」に気づいたときです。

用語の整理をもう少し丁寧にしたいときは、用語集の 再帰（Wiki） もあわせてどうぞ。

自分の言語で手を動かして確かめる

再帰は読むだけでは身につきません。関数の基本を押さえたら、階乗の例を自分で1行ずつ変えて動かすのが確実です。すべてブラウザで実行できる無料レッスンです。

次に読む

← ブログ一覧に戻る