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 method that calls itself
- Recursion is when a method calls itself to solve a smaller piece of the same problem.
- On the AP CSA exam you mostly trace recursion (follow the calls by hand). Writing small recursive methods helps you trace well.
- Every recursive method needs two parts: a base case and a recursive case.
日本語
自身を呼び出すメソッド
- 再帰とは、同じ問題のより小さな部分解決するために、メソッドが自身を呼び出すこと。
- AP CSA試験では主に再帰をトレースする（手動で呼び出しを追跡する）。小さな再帰メソッドを記述することは、トレースを上手に行うのに役立つ。
- すべての再帰メソッドには2つの部分が必要：ベースケースと再帰ケース。
English
Base case and recursive case
- Base case: the simplest input, where you return an answer without calling yourself. This stops the recursion.
- Recursive case: you call the same method with a smaller input, then build the answer.
- Without a base case, the method calls forever and crashes (a stack overflow).
日本語
ベースケースと再帰ケース
- ベースケース：最も単純な入力であり、自身を呼び出さずに答えを返す段階。これが再帰を停止させる。
- 再帰ケース：より小さい入力で同じメソッドを呼び出し、答えを構築する。
- ベースケースがない場合、メソッドが永遠に自身を呼び出してクラッシュする（スタックオーバーフロー）。
English
Example: factorial
factorial(n)meansn * (n-1) * ... * 1. For examplefactorial(4) = 24.- Base case:
factorial(1)is1. - Recursive case:
factorial(n)isn * factorial(n - 1).
日本語
例：階乗
factorial(n)はn * (n-1) * ... * 1を意味する。例えばfactorial(4) = 24。- ベースケース：
factorial(1)は1。 - 再帰的ケース:
factorial(n)はn * factorial(n - 1)となる。
public class Recursion {
public static int factorial(int n) {
if (n <= 1) { // base case
return 1;
}
return n * factorial(n - 1); // recursive case
}
}
English
How the calls unwind
- Each call waits for the smaller call to finish. Then it multiplies and returns.
- Trace
factorial(3). Calls go down, then answers come back up.
日本語
コールの展開
- 各コールはより小さいコールが完了するのを 待つ。その後、掛け算を行って値を返す。
factorial(3)をトレースする。コールは 下 へ進み、答えは 上 へ戻ってくる。
factorial(3) = 3 * factorial(2) <- waits
factorial(2) = 2 * factorial(1) <- waits
factorial(1) = 1 <- base case, returns 1
factorial(2) = 2 * 1 = 2 <- returns 2
factorial(3) = 3 * 2 = 6 <- returns 6
English
Example: sum to n
sumTo(n)adds1 + 2 + ... + n. For examplesumTo(4) = 10.- Base case:
sumTo(0)is0(nothing to add). - Recursive case:
sumTo(n)isn + sumTo(n - 1).
日本語
例: nまでの和
sumTo(n)は1 + 2 + ... + nを加える。例えばsumTo(4) = 10の場合。- ベースケース:
sumTo(0)は0（加えるものがない）。 - 再帰的ケース:
sumTo(n)はn + sumTo(n - 1)となる。
public class Recursion {
public static int sumTo(int n) {
if (n <= 0) { // base case
return 0;
}
return n + sumTo(n - 1); // recursive case
}
}
English
Recursion over an array
- We can also recurse with an index that moves toward the end.
- Base case: when the index is past the last spot, return
0. - Recursive case: add
a[i]to the sum of the rest,arraySum(a, i + 1).
日本語
配列に対する再帰
- インデックスを使って末尾に向かって移動する再帰も可能である。
- ベースケース: インデックスが 最後の位置を超えた 場合、
0を返す。 - 再帰的ケース:
a[i]を残りの和arraySum(a, i + 1)に加える。
English
- To sum the whole array you start at index
0:arraySum(a, 0). - Each call handles one value and trusts the next call for the rest.
日本語
public class Recursion {
public static int arraySum(int[] a, int i) {
if (i >= a.length) { // base case: past the end
return 0;
}
return a[i] + arraySum(a, i + 1);
}
}
- 配列全体を合計するには、インデックス
0から始める:arraySum(a, 0)。 - 各コールは 1つの 値を処理し、残りは次のコールに任せる。
English
Common mistakes
- Recursion needs a base case, or it throws StackOverflowError.
- Each call must move closer to the base case.
日本語
よくあるミス
- 再帰にはベースケースが必要であり、そうでなければ StackOverflowError が発生する。
- 各呼び出しは必ずベースケースに近づかなければなりません。
English
Now you try
- Each task gives you a method skeleton with a TODO. Write the base case and the recursive case.
- A hidden Harness calls your method with several values and checks the result.
- Press Run to compile, then Check answer.
日本語
あなたも試してみよう
- 各タスクには、TODOを含むメソッドの骨格が与えられます。基本ケースと再帰ケースの両方を書いてください。
- 隠されたHarnessがいくつかの値であなたのメソッドを呼び出し、結果を検査します。
- Run を押してコンパイルし、その後 Check answer を押します。
Explore · 探索
Recursion: base + recursive case · 再帰：ベースケース＋再帰ケース
Calls split until a base case, then answers return up. · 基底条件に達するまで分割し、答えを上へ返していきます。
Complete factorial(int n) so it returns n * (n-1) * ... * 1 using recursion. Use a base case for n <= 1. The checker tests several values. · factorial(int n) を完成させ、再帰を使って n * (n-1) * ... * 1 を返すようにしなさい。n <= 1 に対するベースケースを使います。チェッカーは複数の値でテストします。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Complete sumTo(int n) so it returns 1 + 2 + ... + n using recursion. Use a base case for n <= 0. The checker tests several values. · sumTo(int n) を完成させ、再帰を使って 1 + 2 + ... + n を返すようにしなさい。n <= 0 に対するベースケースを使います。チェッカーは複数の値でテストします。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Complete arraySum(int[] a, int i) so it returns the sum of a[i] to the end, using recursion. Base case: when i is past the last spot, return 0. The checker tests several arrays. · arraySum(int[] a, int i)を完成させて、a[i]から終端までの和を返すようにし、再帰を用いて実装してください。ベースケース：iが最終位置を超えた場合は、0を返します。チェッカーは複数の配列をテストします。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。