Recursion: base case and recursive case
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · このページには最新のブラウザ（SharedArrayBuffer対応）が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
English
A function that calls itself
- Recursion is when a function calls itself to solve a smaller version of the same problem.
- It needs two parts: a base case that stops, and a recursive case that shrinks the problem.
- Without a base case, it would call itself forever and crash.
日本語
自身を呼び出す関数
- 再帰とは、関数が同じ問題のより小さなバージョンを解くために自分自身を呼び出すことです。
- 2つの部分が必要です: 停止するためのベースケースと、問題を縮小する再帰ケース。
- ベースケースがないと、無限に自分自身を呼び出してクラッシュします。
English
The base case
- The base case is the smallest problem you can answer directly, with no more calls.
- For factorial,
0!and1!are both1— that is the base case. - Always handle the base case first, so the recursion has somewhere to stop.
日本語
ベースケース
- ベースケースとは、それ以上呼び出しをすることなく直接答えられる最小の問題です。
- 階乗の場合、
0!と1!はどちらも1です — それがベースケースです。 - 再帰が止まる場所があるよう、必ずベースケースを最初に処理してください。
English
The recursive case
- The recursive case solves the problem using the answer to a smaller one.
n! = n × (n - 1)!, sofactorial(n)returnsn * factorial(n - 1).- Each call must move closer to the base case, or it will never stop.
日本語
再帰ケース
- 再帰ケースは、より小さい問題の答えを使って問題を解きます。
n! = n × (n - 1)!なので、factorial(n)はn * factorial(n - 1)を返します。- 各呼び出しは必ずベースケースに近づく必要があります。そうでなければ決して停止しません。
#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;
}
English
Recursion over an array
- You can recurse along an array by passing an index that moves forward each call.
- The base case is "the index has reached the end" (return
0for a sum). - The recursive case is
a[i] + sum(a, i + 1, n)— this item plus the sum of the rest.
日本語
配列に対する再帰
- 配列に沿って再帰するには、各呼び出しで進行するインデックスを渡します。
- ベースケースは「インデックスが終端に達した」(和に対して
0を返す) です。 - 再帰ケースは
a[i] + sum(a, i + 1, n)です — この要素と残りの和の合計。
English
Common mistakes
- Recursion needs a base case, or the call stack overflows.
- Each call must move closer to the base case.
日本語
よくあるミス
- 再帰にはベースケースが必要です。否则、コールスタックがオーバーフローします。
- 各呼び出しは必ずベースケースに近づかなければなりません。
English
Now you try
- Write the base case first, then the recursive case that calls itself on a smaller input.
- Keep test values small so the numbers stay inside an
int. - Do not write a
main— the checker provides one.
日本語
あなたも試してみよう
- まずベースケースを書き、次により小さい入力对自己自身を呼び出す再帰ケースを書きます。
- テスト値を小さく保ち、数字が
intの範囲内に収まるようにします。 mainを書かないでください；チェックツールが用意します。
Explore · 探索
Recursion returns up
Calls split to a base case, then values return up.
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do not write a main.
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 is 1, otherwise base * power(base, exp - 1). Do not write a main.
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Complete int array_sum(const int a[], int i, int n) using recursion: it returns the sum of a[i] up to a[n-1]. Base case: i >= n returns 0. Do not write a main.
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。