再帰の基礎
CoddyのCジャーニー「Fundamentals」セクションの一部 — レッスン 50/63。
再帰は、関数が自分自身を呼び出して問題を解決する手法です。大きな問題を、より小さな似たような問題に分割して解決するようなものです。
階乗を計算する単純な再帰関数の例を見てみましょう：
int factorial(int n) {
// ベースケース：0または1の階乗は1です
if (n <= 1) {
return 1;
}
// 再帰ケース：n! = n * (n-1)!
return n * factorial(n - 1);
}すべての再帰関数には以下が必要です：
- 再帰を停止するためのベースケース
- ベースケースに向かって進む再帰ケース
例えば、factorial(3) を計算する場合：
- factorial(3) は factorial(2) を呼び出します
- factorial(2) は factorial(1) を呼び出します
- factorial(1) は 1 を返します（ベースケース）
- factorial(2) は 2 * 1 = 2 を返します
- factorial(3) は 3 * 2 = 6 を返します
チャレンジ
簡単1からnまでの整数の和を再帰を使って計算する、sumToNという名前の関数を作成してください。
例：
- sumToN(3) は 6 (1 + 2 + 3) を返す必要があります
- sumToN(5) は 15 (1 + 2 + 3 + 4 + 5) を返す必要があります
関数は以下の条件を満たす必要があります：
- nが1の場合をベースケースとし、1を返します
- それ以外の場合は、nに1から(n-1)までの和を足した値を返します
チートシート
再帰は、問題をより小さく似た問題に分割することで解決するために、関数が自分自身を呼び出す手法です。
すべての再帰関数には以下が必要です：
- 再帰を停止するためのベースケース（停止条件）
- ベースケースに向かって進む再帰ケース
例 - 階乗関数：
int factorial(int n) {
// ベースケース：0または1の階乗は1
if (n <= 1) {
return 1;
}
// 再帰ケース：n! = n * (n-1)!
return n * factorial(n - 1);
}factorial(3) の実行プロセス：
- factorial(3) が factorial(2) を呼び出す
- factorial(2) が factorial(1) を呼び出す
- factorial(1) が 1 を返す（ベースケース）
- factorial(2) が 2 * 1 = 2 を返す
- factorial(3) が 3 * 2 = 6 を返す
自分で試してみよう
#include <stdio.h>
// ここに sumToN 関数を記述してください
// main() 関数は変更しないでください
int main() {
int n;
scanf("%d", &n);
printf("%d", sumToN(n));
return 0;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。