再帰の仕組み
ベースケースとコールスタックを学びます。
「再帰の仕組み」はCoddyKit上の無料C Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
再帰とは
再帰とは、関数が問題を解決するために自分自身を呼び出すことです。呼び出すたびに、元の問題のより小さな部分を処理します。
Cでは、最終的に呼び出しを停止する方法があれば、どの関数でも自分自身を呼び出せます。
ベースケース
すべての再帰関数にはベースケースが必要です。これは、自分自身の呼び出しを止めて、直接戻る条件です。
ベースケースがないと、関数は永遠に自分自身を呼び出し続け、プログラムがクラッシュします。
int countdown(int n) {
if (n == 0) return 0; /* base case */
return countdown(n - 1);
}再帰ケース
再帰ケースとは、変更した引数で関数が自分自身を呼び出す部分です。
その引数はベースケースに近づいていかなければなりません。そうでなければ、再帰は終わりません。
int sum_to(int n) {
if (n == 0) return 0; /* base case */
return n + sum_to(n - 1); /* recursive case */
}最初の完全なプログラム
再帰を使って1から5までの数を合計する、完全なプログラムを実行してみましょう。
結果は15になるはずです。
#include <stdio.h>
int sum_to(int n) {
if (n == 0) return 0;
return n + sum_to(n - 1);
}
int main(void) {
printf("%d\n", sum_to(5));
return 0;
}呼び出しを追跡する
再帰は手で追跡すると理解しやすくなります。sum_to(3)の場合：
sum_to(3) = 3 + sum_to(2)
sum_to(2) = 2 + sum_to(1)
sum_to(1) = 1 + sum_to(0)
sum_to(0) = 0
その後、呼び出しは逆向きに戻り、1、3、6という順に結果が返されます。
コールスタック
関数を呼び出すたびに、パラメーターとローカル変数を保持する専用の領域がコールスタック上に確保されます。
深い階層へ進むとスタックフレームが積み重なります。呼び出しが戻ると、そのフレームが削除され、制御が呼び出し元に戻ります。
巻き上げと巻き戻し
再帰には2つの段階があります。巻き上げは、ベースケースに向かって呼び出しが深く進み続ける段階です。
巻き戻しは、ベースケースから戻り、各呼び出しが返された値を使って処理を完了する段階です。
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int main(void) {
printf("%d\n", factorial(4));
return 0;
}戻り値は呼び出し元へ戻る
深い階層の呼び出しが返した値は、その呼び出しを行った側で使われます。
そのため順序が重要です。最も深い呼び出しが最初に完了し、スタックを戻る途中で結果が組み合わされます。
int power(int base, int exp) {
if (exp == 0) return 1;
return base * power(base, exp - 1);
}再帰中に出力する
再帰呼び出しの前でも後でも出力できます。前に出力すると数値が下っていく順に表示され、後に出力すると戻ってくる順に表示されます。
#include <stdio.h>
void down(int n) {
if (n == 0) return;
printf("%d ", n);
down(n - 1);
}
int main(void) {
down(5);
printf("\n");
return 0;
}戻りながら出力する
printfを再帰呼び出しの後に移動すると、順序が逆になります。最も深い呼び出しが最初に出力されます。
これにより、5 4 3 2 1ではなく1 2 3 4 5と出力されます。
#include <stdio.h>
void up(int n) {
if (n == 0) return;
up(n - 1);
printf("%d ", n);
}
int main(void) {
up(5);
printf("\n");
return 0;
}覚えておくべき2つのルール
正しい再帰関数は、次の2つのルールに従います。
1. 再帰せずに戻るベースケースが少なくとも1つある。
2. すべての再帰呼び出しで、引数がベースケースに近づく。
どちらかのルールを破ると、プログラムは永遠にループします。
クイックチェック
再帰の基本を理解できているか確認しましょう。
まとめ
再帰では、より小さな入力に対して自分自身を呼び出すことで問題を解決します。停止するためのベースケースと、そこに近づいていく再帰ケースが必ず必要です。
呼び出しごとにスタックフレームが使われ、再帰が巻き戻されると結果が戻ってきます。
よくある質問
「再帰の仕組み」レッスンは無料ですか？
はい。「再帰の仕組み」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「再帰の仕組み」で何を学びますか？
ベースケースとコールスタックを学びます。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「再帰の仕組み」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。