もう怖くない！C言語の再帰処理 - 基本構造と無限ループ対策をやさしく解説-Next Hello

さてさて、プログラミングの世界には色々なテクニックがありますが、中でもちょっと不思議なのが「C言語の再帰処理（さいきしょり）」です。

一言でいうと、関数の中で、その関数自身をもう一度呼び出す、という処理のこと。
「え？自分で自分を呼ぶってどういうこと？」って思いますよね。大丈夫、最初はみんなそう思います！

例えるなら、合わせ鏡をイメージしてみてください。

鏡の中に映った鏡、そのまた中に映った鏡…と、同じものが繰り返されていく感じ。
あるいは、ロシアのマトリョーシカ人形。

人形を開けると中に同じような人形がいて、それを開けるとまた…という構造に似ていますね。

プログラムの世界では、関数Aが処理の途中で、もう一度関数Aを呼び出す、といった形で使われます。

ちょっとトリッキーに見えるかもしれませんが、この仕組みをうまく使うと、複雑に見える問題をスッキリと解けたり、コードが読みやすくなったりすることがあるんです。

まずは「ふーん、関数が自分を呼び出すのかー」くらいの感じで、頭の片隅に置いておいてくださいね。

なぜC言語で再帰処理を使うの？メリット・デメリット

「自分で自分を呼ぶなんて、ややこしそう…ループ処理じゃダメなの？」と思うかもしれません。

もちろん、ループ処理（for文やwhile文など）で書けることの方が多いです。でも、再帰処理には再帰処理ならではの良さがあるんです。もちろん、気をつける点もあります。

再帰処理を使うメリット

特定の種類の問題（特に、構造が再帰的なもの。例えばフォルダの中のフォルダを探す、みたいな）は、ループで書くよりコードが直感的でシンプルになる場合があります。
アルゴリズムによっては、再帰で考えた方が自然で理解しやすいこともあります。

再帰処理を使うデメリット

関数を呼び出すのにはコストがかかるので、ループ処理に比べて動きが遅くなったり、メモリをたくさん使ったりする傾向があります。（後で説明する「スタックオーバーフロー」の原因にもなりえます）
処理の流れが追いかけにくく、デバッグ（間違い探し）が少し大変になることがあります。
単純な繰り返しなら、ループ処理の方が効率的なことが多いです。

つまり、何でもかんでも再帰で書けば良いというわけではなく、問題の性質や状況によってループ処理と使い分けるのが賢いやり方、というわけですね。

最初は「こんな考え方もあるんだな」くらいでOKですよ！

C言語での再帰処理の基本的な書き方【構文解説】

さあ、いよいよC言語で再帰処理をどう書くか、見ていきましょう！

再帰関数（自分自身を呼び出す関数）を作るには、大きく分けて2つの重要な部品が必要になります。

終了条件（ベースケース）：もう再帰呼び出しをしないよ、という終わりの条件。
再帰ステップ：自分自身を呼び出して、問題を少し小さな形にする部分。

この2つが揃っていないと、関数は無限に自分を呼び出し続けてしまったり、そもそも動かなかったりします。

イメージとしては、こんな感じの構造になります。

// 再帰関数の基本的な形（イメージ）

戻り値の型 関数名(引数) {
    // 1. 終了条件（ベースケース）
    if (ある条件を満たしたら) {
        // 再帰呼び出しをせずに、特定の値を返す（または処理を終える）
        return 終了時の値;
    }
    // 2. 再帰ステップ
    else {
        // 引数を変化させながら、自分自身を呼び出す
        // 必要であれば、呼び出した結果を使って何か処理をする
        戻り値の型 結果 = 関数名(変化させた引数);
        return 結果を使った値; // または return 関数名(変化させた引数); の場合も
    }
}

「ある条件を満たしたら」というのがベースケース、「関数名(変化させた引数)」というのが再帰ステップですね。

この2つの部品について、もう少し詳しく見ていきましょう！

【必須要素1】終了条件（ベースケース）

再帰処理において、めちゃくちゃ大事なのが、この「終了条件」、別名「ベースケース」です。
これは、再帰呼び出しの「出口」や「ストッパー」の役割を果たします。

もしベースケースがなかったり、あっても条件がいつまでも満たされなかったりすると、関数は永遠に自分自身を呼び出し続けることになります。これは「無限ループ」ならぬ「無限再帰」状態で、プログラムは止まらなくなってしまいます（実際には後述のスタックオーバーフローで強制終了することが多いです）。

例えば、「nが0になったら終わり」というような、必ずいつかは到達する条件を設定します。

// ベースケースの例
if (n == 0) {
    return 1; // nが0になったら、1を返して処理終了！
}

この「出口」の設定を忘れないように、しっかり意識しましょうね！

【必須要素2】再帰ステップ

もう一つの部品が「再帰ステップ」です。

これは、関数が自分自身を呼び出す部分のこと。
ただ呼び出すだけじゃなくて、大事なポイントがあります。

それは、呼び出すたびに、少しずつ問題を小さくしていく（＝終了条件に近づけていく）ということです。

例えば、引数 `n` を使っているなら、次に呼び出すときは `n-1` を渡す、といった具合です。
こうすることで、呼び出しが繰り返されるうちに、いずれ引数が変化して終了条件（例えば `n == 0`）を満たすようになります。

// 再帰ステップの例
// nを1減らして、自分自身をもう一度呼び出す
result = n * calculate_something(n - 1);

呼び出すたびに、ちゃんとゴール（ベースケース）に向かって進んでいるか、ここをしっかり設計するのが再帰処理のキモになりますよ。

【実践】C言語の再帰処理 - サンプルコードで学ぼう

理屈は何となくわかった！…けど、やっぱり実際にコードを見てみないとピンときませんよね。

ここでは、C言語の再帰処理を使った簡単な例を2つ紹介します。

実際に手を動かして、コードを書いて、動かしてみるのが一番の近道ですよ！

例1：階乗を計算する再帰関数

まずは、数学でおなじみの「階乗（かいじょう）」を計算するプログラムです。

階乗は、例えば 3! = 3 * 2 * 1 = 6 のように、1からその数までの整数をすべて掛け合わせる計算ですね。
（ちなみに 0! は 1 と定義されています）

これを再帰で考えると、n! = n * (n-1)! という関係が成り立ちます。（例えば 3! = 3 * 2!）
そして、ベースケースは 0! = 1 ですね。これをコードにしてみましょう。

#include <stdio.h>

// 階乗を計算する再帰関数
int factorial(int n) {
    // ベースケース：nが0なら1を返す
    if (n == 0) {
        printf("ベースケース到達！ factorial(0) は 1 を返します。\n");
        return 1;
    }
    // 再帰ステップ：n * factorial(n-1) を計算する
    else {
        printf("factorial(%d) を呼び出しました。%d * factorial(%d) を計算します。\n", n, n, n - 1);
        int result = n * factorial(n - 1); // ここで自分自身を呼び出し！
        printf("factorial(%d) の計算結果 %d を返します。\n", n, result);
        return result;
    }
}

int main() {
    int num = 3;
    printf("%d の階乗を計算します。\n", num);
    int answer = factorial(num);
    printf("%d の階乗は %d です。\n", num, answer);
    return 0;
}

▼実行結果の例▼

3 の階乗を計算します。
factorial(3) を呼び出しました。3 * factorial(2) を計算します。
factorial(2) を呼び出しました。2 * factorial(1) を計算します。
factorial(1) を呼び出しました。1 * factorial(0) を計算します。
ベースケース到達！ factorial(0) は 1 を返します。
factorial(1) の計算結果 1 を返します。
factorial(2) の計算結果 2 を返します。
factorial(3) の計算結果 6 を返します。
3 の階乗は 6 です。

どうでしょうか？ `factorial(3)` が `factorial(2)` を呼び、`factorial(2)` が `factorial(1)` を呼び… と順番に呼び出され、最後に `factorial(0)` が 1 を返すと、今度は逆順に計算結果が返っていく様子がわかると思います。

関数の動きを紙に書き出して、引数や戻り値がどう変化するかを追ってみると、理解がグッと深まりますよ。

例2：フィボナッチ数列を求める再帰関数

次も有名な例、「フィボナッチ数列」です。

これは、最初の2つの項が 0 と 1 で、それ以降の項は直前の2つの項の和になる、という数列です。(0, 1, 1, 2, 3, 5, 8, 13, ...)

n番目のフィボナッチ数を F(n) とすると、
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n >= 2)

という関係があります。これがそのまま再帰関数の定義になりますね！
F(0) と F(1) がベースケース、F(n) = F(n-1) + F(n-2) が再帰ステップです。

#include <stdio.h>

// フィボナッチ数列の第n項を求める再帰関数
int fibonacci(int n) {
    printf("fibonacci(%d) が呼び出されました。\n", n);
    // ベースケース 1: nが0なら0を返す
    if (n == 0) {
        printf("ベースケース: fibonacci(0) は 0 を返します。\n");
        return 0;
    }
    // ベースケース 2: nが1なら1を返す
    else if (n == 1) {
        printf("ベースケース: fibonacci(1) は 1 を返します。\n");
        return 1;
    }
    // 再帰ステップ: fibonacci(n-1) + fibonacci(n-2) を計算する
    else {
        printf("fibonacci(%d) は fibonacci(%d) + fibonacci(%d) を計算します。\n", n, n - 1, n - 2);
        int result = fibonacci(n - 1) + fibonacci(n - 2); // ここで2回呼び出し！
        printf("fibonacci(%d) の計算結果 %d を返します。\n", n, result);
        return result;
    }
}

int main() {
    int num = 4; // 4番目 (0から数えて) のフィボナッチ数を求める
    printf("%d 番目のフィボナッチ数を計算します。\n", num);
    int answer = fibonacci(num);
    printf("%d 番目のフィボナッチ数は %d です。\n", num, answer);
    return 0;
}

▼実行結果の例 (n=4 の場合)▼

4 番目のフィボナッチ数を計算します。
fibonacci(4) が呼び出されました。
fibonacci(4) は fibonacci(3) + fibonacci(2) を計算します。
fibonacci(3) が呼び出されました。
fibonacci(3) は fibonacci(2) + fibonacci(1) を計算します。
fibonacci(2) が呼び出されました。
fibonacci(2) は fibonacci(1) + fibonacci(0) を計算します。
fibonacci(1) が呼び出されました。
ベースケース: fibonacci(1) は 1 を返します。
fibonacci(0) が呼び出されました。
ベースケース: fibonacci(0) は 0 を返します。
fibonacci(2) の計算結果 1 を返します。
fibonacci(1) が呼び出されました。
ベースケース: fibonacci(1) は 1 を返します。
fibonacci(3) の計算結果 2 を返します。
fibonacci(2) が呼び出されました。
fibonacci(2) は fibonacci(1) + fibonacci(0) を計算します。
fibonacci(1) が呼び出されました。
ベースケース: fibonacci(1) は 1 を返します。
fibonacci(0) が呼び出されました。
ベースケース: fibonacci(0) は 0 を返します。
fibonacci(2) の計算結果 1 を返します。
fibonacci(4) の計算結果 3 を返します。
4 番目のフィボナッチ数は 3 です。

実行結果を見ると、`fibonacci(2)` が2回呼び出されているなど、同じ計算が何度も行われているのがわかりますか？
このように、単純な再帰は効率が悪くなることがある、というのも知っておくと良い点です。（これを改善する方法もあるのですが、それはまた別の機会に！）

C言語で再帰処理を使う際の注意点【無限ループ・スタックオーバーフロー】

さて、再帰処理の便利さを見てきましたが、使う上でいくつか注意すべき「落とし穴」があります。

特に初心者がハマりやすいのが「無限ループ（無限再帰）」と「スタックオーバーフロー」です。

これらを知っておかないと、プログラムが意図せず止まらなくなったり、エラーで落ちたりしてしまいます。

しっかり対策を学びましょう！

無限ループを防ぐには？

無限ループ（この場合は無限再帰）は、その名の通り、関数が延々と自分自身を呼び出し続けてしまう状態です。

主な原因は、

ベースケース（終了条件）を書き忘れている。
ベースケースの条件が間違っていて、いつまで経っても満たされない。
再帰ステップでの引数の変化が、ベースケースに向かわない。

といった単純なミスが多いです。

対策はシンプル！

ベースケースを絶対に書く！ まず最初にベースケースの処理を書く癖をつけると良いかもしれません。
引数が呼び出しごとに必ずベースケースの条件に近づいていくか、頭の中や紙の上でシミュレーションしてみる。
怪しいなと思ったら、関数の中で `printf` などを使って、引数の値がどう変化しているか表示させてみる。（デバッグの基本ですね！）

うっかりミスで無限ループ地獄にハマらないように、特にベースケースの設定はしっかり確認しましょうね。

スタックオーバーフローとは？その対策

もう一つの注意点が「スタックオーバーフロー」です。

「スタック？」ってなりますよね。簡単に言うと、プログラムが関数を呼び出すときに使う、作業用のメモリ領域（机の上みたいなもの）だと考えてください。

関数を呼び出すたびに、その関数の情報（どこまで処理したか、変数の値など）が、この「スタック」と呼ばれる領域に積み重ねられていきます。

再帰処理で関数が何度も何度も深く呼び出されると、このスタック領域に情報がどんどん積み重なっていきます。

そして、用意されたスタック領域がいっぱいになってしまうと…「もう載せきれない！」となってエラーが発生します。これがスタックオーバーフローです。（積み上げた積み木が崩れるイメージです）

スタックオーバーフローを防ぐための対策は、

あまりにも深い再帰呼び出し（何万回も呼び出すような）は避ける設計にする。
可能であれば、ループ処理で書き換えられないか検討する。（大抵の場合、再帰はループで書き換え可能です）
（少し高度な話ですが、末尾再帰という書き方をすると、コンパイラが最適化してスタックを消費しないコードに変換してくれる場合があります。ただ、C言語のコンパイラが必ず対応しているとは限りません。）

特に、フィボナッチ数列の単純な再帰実装は、nが大きくなると爆発的に呼び出し回数が増えるため、スタックオーバーフローを起こしやすい例として知られています。

深すぎる再帰はパソコンにも限界がある、ということを覚えておきましょう。

【まとめ】C言語の再帰処理を理解してステップアップ！

お疲れ様でした！今回はC言語の再帰処理について、基本の考え方から、具体的な書き方、そして注意点までを見てきました。

もう一度ポイントをおさらいしましょう。

再帰処理は、関数が自分自身を呼び出す処理のこと。
「ベースケース（終了条件）」と「再帰ステップ（自分を呼び出す処理）」の2つがセットで必要。
コードが簡潔になるなどのメリットがある一方、無限ループやスタックオーバーフローには注意が必要。
無限ループを防ぐには、ベースケースの確実な設定がカギ。
スタックオーバーフローは、呼び出しが深くなりすぎないように気をつける。

最初はちょっと難しく感じるかもしれませんが、再帰処理はアルゴリズムの世界では非常によく使われる考え方です。

この考え方に慣れておくと、より複雑な問題に取り組むときにきっと役立ちます。
「もう怖くない！」と思えるようになったら、次はぜひ、自分で簡単な再帰関数を書いてみたり、他のアルゴリズム（例えば、木構造の探索など）で再帰がどう使われているか調べてみたりするのも良いでしょう。

これであなたも再帰マスターへの第一歩を踏み出しました！どんどんコードを書いて、試して、C言語の世界をもっと楽しんでくださいね！

【関連記事】

>> C言語とは？特徴・できること・学ぶメリット

もう怖くない！C言語の再帰処理 - 基本構造と無限ループ対策をやさしく解説