このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
自身を呼び出す関数
- 再帰とは、関数が同じ問題のより小さなバージョンを解くために自分自身を呼び出すことです。
- 2つの部分が必要です: 停止するためのベースケースと、問題を縮小する再帰ケース。
- ベースケースがないと、無限に自分自身を呼び出してクラッシュします。
ベースケース
- ベースケースとは、それ以上呼び出しをすることなく直接答えられる最小の問題です。
- 階乗の場合、
0!と1!はどちらも1です — それがベースケースです。 - 再帰が止まる場所があるよう、必ずベースケースを最初に処理してください。
再帰ケース
- 再帰ケースは、より小さい問題の答えを使って問題を解きます。
n! = n × (n - 1)!なので、factorial(n)はn * factorial(n - 1)を返します。- 各呼び出しは必ずベースケースに近づく必要があります。そうでなければ決して停止しません。
English
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main(void) {
printf("%d\n", factorial(5)); // 120
return 0;
}
配列に対する再帰
- 配列に沿って再帰するには、各呼び出しで進行するインデックスを渡します。
- ベースケースは「インデックスが終端に達した」(和に対して
0を返す) です。 - 再帰ケースは
a[i] + sum(a, i + 1, n)です — この要素と残りの和の合計。
よくあるミス
- 再帰にはベースケースが必要です。否则、コールスタックがオーバーフローします。
- 各呼び出しは必ずベースケースに近づかなければなりません。
あなたも試してみよう
- まずベースケースを書き、次により小さい入力对自己自身を呼び出す再帰ケースを書きます。
- テスト値を小さく保ち、数字が
intの範囲内に収まるようにします。 mainを書かないでください;チェックツールが用意します。
探索
再帰は上方向に戻ってくる
ベースケースまで分割を呼び出し、その後値が上方向に戻ってくる。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
再帰を使ってint factorial(int n)を完成させる:n <= 1(ベースケース)に対しては1を返す、それ以外の場合はn * factorial(n - 1)を返す。mainは書かない。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
再帰を使ってint power(int base, int exp)を完成させる(exp >= 0と仮定):baseの0乗は1、それ以外の場合はbase * power(base, exp - 1)。mainは書かない。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
再帰を使ってint array_sum(const int a[], int i, int n)を完成させる:a[i]からa[n-1]までの和を返す。ベースケース:i >= nは0を返す。mainは書かない。
実行ボタンをクリックして出力を確認してください。