古典的な再帰問題
階乗とフィボナッチ数列を扱います。
「古典的な再帰問題」はCoddyKit上の無料C Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
古典的な問題
問題によっては、再帰に自然に適しています。定番の問題を学ぶと、再利用できるパターンが身につきます。
このレッスンでは、階乗、フィボナッチ数、各桁の合計、最大公約数、出力の反転を扱います。
階乗
nの階乗とは、nにn-1の階乗を掛けたものです。1!は1です。
これは、明確なベースケースと1回の再帰呼び出しを持つ、教科書的な再帰の例です。
#include <stdio.h>
long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int main(void) {
printf("%ld\n", factorial(6));
return 0;
}フィボナッチ数
フィボナッチ数は、それ以前の2つの数の和です。再帰による定義では、fib(0)=0とfib(1)=1という2つのベースケースが必要です。
この方法では、1ステップごとに2回呼び出します。
int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}フィボナッチ数を実行する
完全なプログラムを見てみましょう。fib(10)は55を出力するはずです。
この単純な実装は同じ計算を繰り返すため、nが大きいと遅くなります。
#include <stdio.h>
int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
int main(void) {
printf("%d\n", fib(10));
return 0;
}各桁の合計
数値の各桁を足すには、n % 10で最後の桁を取り出し、n / 10で残りの数に対して再帰します。
ベースケースは、nが0になったときです。
int digit_sum(int n) {
if (n == 0) return 0;
return (n % 10) + digit_sum(n / 10);
}各桁の合計を実行する
1234の場合、合計は1+2+3+4 = 10です。完全なプログラムで確認してみましょう。
#include <stdio.h>
int digit_sum(int n) {
if (n == 0) return 0;
return (n % 10) + digit_sum(n / 10);
}
int main(void) {
printf("%d\n", digit_sum(1234));
return 0;
}最大公約数
ユークリッドの互除法は、再帰に自然に適しています。aとbの最大公約数は、bとa % bの最大公約数と等しくなります。
bが0になったとき、aが答えです。
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}最大公約数の完全なプログラム
48と18の最大公約数は6です。このプログラムはその値を出力します。
#include <stdio.h>
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main(void) {
printf("%d\n", gcd(48, 18));
return 0;
}数値を反転する
再帰は出力にも利用できます。再帰呼び出しの後に最後の桁を出力すると、処理の順序を自然に逆転できます。
このヘルパーは、再帰を使って数値の各桁を1行ずつ出力します。
#include <stdio.h>
void print_digits(int n) {
if (n == 0) return;
print_digits(n / 10);
printf("%d ", n % 10);
}
int main(void) {
print_digits(729);
printf("\n");
return 0;
}べき乗関数
底を指数でべき乗する処理も再帰的に定義できます。base^exp は、base に base^(exp-1) を掛けたものです。
基底ケースは指数が 0 の場合で、1 を返します。
long power(int base, int exp) {
if (exp == 0) return 1;
return base * power(base, exp - 1);
}再利用できるパターン
共通する形に注目してください。まず基底ケースを確認し、現在のステップと、より小さい問題への呼び出し結果を組み合わせます。
このパターンに気づけば、多くの問題を短い再帰関数で解決できます。
理解度チェック
正しい基底ケースを選んでください。
まとめ
階乗、フィボナッチ数列、各桁の和、最大公約数、べき乗はすべて、1つの再帰パターンを共有しています。基底ケースを処理し、現在の値と、より小さい部分問題の結果を組み合わせます。
これらのテンプレートは、他の多くの処理にも応用できます。
よくある質問
「古典的な再帰問題」レッスンは無料ですか？
はい。「古典的な再帰問題」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「古典的な再帰問題」で何を学びますか？
階乗とフィボナッチ数列を扱います。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「古典的な再帰問題」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 再帰の仕組み
- 古典的な再帰問題
- 再帰と反復の比較
- スタックオーバーフローを防ぐ