再帰と反復の比較
それぞれを選ぶ場面を学びます。
「再帰と反復の比較」はCoddyKit上の無料C Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
繰り返し処理の2つの方法
多くの問題は、再帰または反復のどちらでも解決できます。反復ではループを使い、再帰では関数呼び出しを使います。
どちらでも同じ結果を得られますが、書き方、メモリ使用量、速度が異なります。
ループによる階乗
これは for ループを使って反復的に書いた階乗です。関数自身を呼び出すことはなく、1つの変数で積を累積します。
#include <stdio.h>
long factorial(int n) {
long result = 1;
for (int i = 2; i <= n; i++)
result *= i;
return result;
}
int main(void) {
printf("%ld\n", factorial(6));
return 0;
}再帰による階乗
再帰版はより短く、数学的な定義をそのまま表しています。
factorial(6) はどちらも 720 を出力しますが、使っている仕組みは異なります。
long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}メモリ使用量の違い
反復では通常、少数のローカル変数だけを使うため、固定された少量のメモリで済みます。
再帰では呼び出しごとにスタックフレームが追加されるため、深い再帰ほど多くのメモリを使い、スタック領域を使い切る可能性があります。
速度の違い
再帰呼び出しには、フレームの準備と復帰に伴う小さなコストがあります。
単純なカウント処理では、呼び出しのオーバーヘッドを避けられるループのほうが、少し高速なことがよくあります。
再帰が適している場合
再帰は、木構造、入れ子構造、分割統治アルゴリズムなど、問題自体が自然に再帰的な場合に力を発揮します。
そのような場合、手動スタックを使った同等のループよりも、再帰コードのほうが短く明快です。
反復が適している場合
配列の合計やカウントのような単純な線形反復では、ループのほうが簡単で、メモリ使用量も一定です。
また、大きな入力に対するスタックオーバーフローのリスクもありません。
int sum_array(int a[], int n) {
int total = 0;
for (int i = 0; i < n; i++)
total += a[i];
return total;
}同じ処理を2つの書き方で
1 から n までの合計は、どちらの方法でも求められます。これは再帰と同じ答えを返す反復版です。
#include <stdio.h>
int sum_to(int n) {
int total = 0;
for (int i = 1; i <= n; i++)
total += i;
return total;
}
int main(void) {
printf("%d\n", sum_to(100));
return 0;
}再帰をループに変換する
再帰はすべて反復に書き換えられます。その際、自分で明示的なスタックを使うこともあります。
階乗や合計のような単純な線形再帰は、累積用の変数を使った通常のループに変換できます。
#include <stdio.h>
int main(void) {
int n = 5, result = 1;
while (n > 1) { result *= n; n--; }
printf("%d\n", result);
return 0;
}末尾再帰について
末尾再帰呼び出しとは、関数内で最後に行われる処理が関数呼び出しになっているものです。コンパイラによっては、これをループに最適化して、1つのフレームを再利用できます。
C ではこれが保証されないため、深い再帰で頼りにしてはいけません。
int sum_tail(int n, int acc) {
if (n == 0) return acc;
return sum_tail(n - 1, acc + n);
}方法を選ぶ
問題が自然に入れ子構造や分割統治になっていますか。その場合は再帰が適しています。
単純な線形反復で、入力が非常に大きくなる可能性がありますか。その場合は、反復のほうが安全で、多くの場合高速です。
理解度チェック
2つの方法を比較してください。
まとめ
再帰と反復は、同じ問題を解決できます。ループはメモリ使用量が一定で、線形処理に適しています。再帰は入れ子構造や分割統治問題を明快に表せますが、呼び出しごとにスタックフレームを消費します。
よくある質問
「再帰と反復の比較」レッスンは無料ですか？
はい。「再帰と反復の比較」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「再帰と反復の比較」で何を学びますか？
それぞれを選ぶ場面を学びます。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「再帰と反復の比較」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 再帰の仕組み
- 古典的な再帰問題
- 再帰と反復の比較
- スタックオーバーフローを防ぐ