再帰の基礎
CoddyのCジャーニー「基礎」セクションの一部。レッスン 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)までの数の合計を足した値を返す
自分で試してみよう
#include <stdio.h>
// ここにsumToN関数を書いてください
// main()関数を変更しないでください
int main() {
int n;
scanf("%d", &n);
printf("%d", sumToN(n));
return 0;
}このレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
基礎のすべてのレッスン
自分で練習してみよう: Cオンラインコンパイラ