C++の再帰関数を完全攻略！初心者でも仕組みと応用がわかる徹底ガイド
生徒
「C++で『自分自身を呼び出す関数』があるって聞いたんですけど、それって無限ループにならないんですか？」
先生
「それは『再帰関数（さいきかんすう）』ですね。正しく終わりを決めてあげれば、複雑な問題を驚くほどスッキリ解決できるんですよ。」
生徒
「自分の中で自分を呼ぶなんて、合わせ鏡みたいで不思議です。具体的にどう使うんですか？」
先生
「マトリョーシカ人形をイメージすると分かりやすいです。基本的な仕組みから応用まで、一緒に見ていきましょう！」
1. 再帰関数とは？自分を呼び出す魔法の仕組み
C++の再帰関数（さいきかんすう）とは、関数の中で自分自身の関数を再び呼び出す手法のことです。英語では「Recursion」と呼びます。プログラミング未経験でパソコンを触ったことがない方でも、日常の風景で例えるとすぐに理解できます。
例えば、大きな箱の中に小さな箱が入っていて、その中にさらに小さな箱が入っている様子を想像してください。「一番小さな箱を見つけるまで、箱を開け続ける」という動作は再帰的です。自分が行っている作業（箱を開ける）の中に、全く同じ作業（さらに箱を開ける）が含まれているからです。C++のプログラムでも、このように「大きな問題を、同じ形をした小さな問題に分解して解く」ときに再帰関数が使われます。アルゴリズム（問題を解く手順）を考える上で、非常に強力な武器になります。
2. 再帰に欠かせない「停止条件」と「再帰ステップ」
再帰関数を作るには、絶対に忘れてはいけない2つのルールがあります。これがないと、プログラムは無限に自分を呼び出し続け、パソコンがパニックを起こして止まってしまいます（これをスタックオーバーフローと呼びます）。
一つ目は停止条件（ベースケース）です。これは「これ以上自分を呼ばない」という終わりの合図です。マトリョーシカであれば「中身がもうない一番小さな人形にたどり着いたとき」が停止条件になります。二つ目は再帰ステップです。これは、問題を少しずつ小さくしながら自分を呼び出す部分です。この2つを正しく組み合わせることで、再帰関数は安全に動作します。C++の関数の基礎知識があれば、if文を使って簡単にこの条件を作ることができます。
3. 最初の実例：カウントダウンを表示しよう
まずは、指定した数字から1までカウントダウンし、最後に「発射！」と表示するシンプルな再帰関数を見てみましょう。繰り返し処理（ループ）を使わずに、自分を呼び出すことでカウントを進めます。
#include <iostream>
// カウントダウンを行う再帰関数
void countDown(int n) {
// 停止条件：数字が0になったら終わり
if (n <= 0) {
std::cout << "発射！" << std::endl;
return;
}
// 今の数字を表示
std::cout << n << "..." << std::endl;
// 再帰ステップ：数字を1減らして自分自身を呼び出す
countDown(n - 1);
}
int main() {
countDown(3); // 3からカウントダウン開始
return 0;
}
3...
2...
1...
発射！
このプログラムでは、countDown(3)が呼ばれると、その中でcountDown(2)を呼び、さらにその中でcountDown(1)を呼びます。最後にcountDown(0)が呼ばれたとき、if文の条件に一致して「発射！」と表示され、魔法の連鎖が終了します。
4. 数学の応用：階乗（かいじょう）の計算
再帰関数がよく使われる定番の例に、数学の階乗（かいじょう）があります。階乗とは、ある数字から1までをすべて掛け合わせたものです（例：5の階乗は 5×4×3×2×1 = 120）。
「nの階乗」は、「n × (n-1)の階乗」と言い換えることができます。この「同じ形の小さな問題」という性質が再帰にピッタリです。計算結果を戻り値として返すタイプの再帰関数を作ってみましょう。
#include <iostream>
// 階乗を計算する関数
int factorial(int n) {
// 停止条件：1になったら1を返す
if (n <= 1) {
return 1;
}
// 再帰ステップ：n と (n-1)の階乗を掛け合わせる
return n * factorial(n - 1);
}
int main() {
int number = 5;
int result = factorial(number);
std::cout << number << "の階乗は " << result << " です。" << std::endl;
return 0;
}
5の階乗は 120 です。
このコードでは、プログラムが計算を「予約」していくような動きをします。5×(4×(3×(2×(1))))という風に、奥まで行ってから答えを持って帰ってくるイメージです。デバッグ（プログラムのミス探し）の際はこの動きを追うのがコツです。
5. メモリの仕組み「スタック」を知っておこう
再帰関数が動いている間、パソコンの中ではスタックというメモリ領域が使われています。スタックはお皿を積み重ねるような構造をしていて、関数が呼ばれるたびにお皿が上に積まれ、終わると上から取り除かれます。
再帰が深すぎると（何万回も自分を呼ぶと）、このお皿の山が高くなりすぎて崩れてしまいます。これが先ほど触れた「スタックオーバーフロー」の正体です。パソコン初心者の人は、「再帰は便利だけど、あまりに深い繰り返しには向かないこともある」と覚えておいてください。大量のデータを扱うときは、for文やwhile文といった通常の繰り返し処理の方が安全な場合もあります。
6. 発展的な応用：フィボナッチ数列
再帰関数の面白さが一番わかるのがフィボナッチ数列です。これは「前の2つの数字を足すと次の数字になる」という不思議な数列です（1, 1, 2, 3, 5, 8, 13...）。自然界のひまわりの種の並びなどにも現れる有名な数です。
「n番目の数字」を知るには「(n-1)番目」と「(n-2)番目」を足せばいい、という考え方をそのままプログラムにできます。コードがとても美しく見えるのが再帰の魅力です。
#include <iostream>
// n番目のフィボナッチ数を求める
int fibonacci(int n) {
// 停止条件：1番目か2番目なら1を返す
if (n <= 2) {
return 1;
}
// 再帰ステップ：前の2つを足す
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int index = 6;
std::cout << index << "番目のフィボナッチ数は " << fibonacci(index) << " です。" << std::endl;
return 0;
}
6番目のフィボナッチ数は 8 です。
このように、複雑な規則性をたった数行で表現できるのが再帰の凄さです。Google検索エンジンなどの複雑なシステムでも、こうした数学的なアルゴリズムが応用されています。
7. 文字列を逆さまにする再帰のテクニック
数字だけでなく、文字（文字列）に対しても再帰は有効です。例えば、入力された文字を逆から順番に表示する処理を考えてみましょう。「最初の1文字を表示するのを後回しにして、残りの文字を先に処理する」という工夫をします。
#include <iostream>
#include <string>
// 文字列を逆順に表示する再帰関数
void reversePrint(std::string str) {
// 停止条件：文字が空になったら終わり
if (str.length() == 0) {
return;
}
// 再帰ステップ：2文字目以降を先に渡す（substringは部分的な取り出し）
reversePrint(str.substr(1));
// 後回しにしていた「最初の1文字」を最後に表示
std::cout << str[0];
}
int main() {
std::string text = "C++Programming";
std::cout << "逆さまにすると: ";
reversePrint(text);
std::cout << std::endl;
return 0;
}
逆さまにすると: gnimmargorP++C
関数の呼び出しの「後」に処理を書くことで、深いところから戻ってくる瞬間に実行されるという面白い性質を利用しています。これは後順走査的な考え方で、データの並べ替えなどに役立ちます。
8. 再帰関数を使いこなすためのアドバイス
再帰関数は、パズルのような楽しさがありますが、初心者のうちは「今どこまで深く潜っているのか」を整理するのが大変です。そんな時は、紙に図を書いて、一つひとつの呼び出しを追いかけてみるのが一番の近道です。また、変数の値がどのように変化しているかを確認することも重要です。
最近のC++開発では、スピードを優先するために再帰を避けることもありますが、フォルダの中のファイルをすべて探す処理や、複雑なデータの整理（ソート）など、再帰を使ったほうが圧倒的にシンプルに書ける場面もたくさんあります。まずは簡単なカウントダウンから始めて、少しずつ自分を呼び出す魔法に慣れていってくださいね！
