このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
自身を呼び出すメソッド
- 再帰とは、同じ問題のより小さな部分解決するために、メソッドが自身を呼び出すこと。
- AP CSA試験では主に再帰をトレースする(手動で呼び出しを追跡する)。小さな再帰メソッドを記述することは、トレースを上手に行うのに役立つ。
- すべての再帰メソッドには2つの部分が必要:ベースケースと再帰ケース。
ベースケースと再帰ケース
- ベースケース:最も単純な入力であり、自身を呼び出さずに答えを返す段階。これが再帰を停止させる。
- 再帰ケース:より小さい入力で同じメソッドを呼び出し、答えを構築する。
- ベースケースがない場合、メソッドが永遠に自身を呼び出してクラッシュする(スタックオーバーフロー)。
例:階乗
factorial(n)はn * (n-1) * ... * 1を意味する。例えばfactorial(4) = 24。- ベースケース:
factorial(1)は1。 - 再帰的ケース:
factorial(n)はn * factorial(n - 1)となる。
English
public class Recursion {
public static int factorial(int n) {
if (n <= 1) { // base case
return 1;
}
return n * factorial(n - 1); // recursive case
}
}
コールの展開
- 各コールはより小さいコールが完了するのを 待つ。その後、掛け算を行って値を返す。
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
例: nまでの和
sumTo(n)は1 + 2 + ... + nを加える。例えばsumTo(4) = 10の場合。- ベースケース:
sumTo(0)は0(加えるものがない)。 - 再帰的ケース:
sumTo(n)はn + sumTo(n - 1)となる。
English
public class Recursion {
public static int sumTo(int n) {
if (n <= 0) { // base case
return 0;
}
return n + sumTo(n - 1); // recursive case
}
}
配列に対する再帰
- インデックスを使って末尾に向かって移動する再帰も可能である。
- ベースケース: インデックスが 最後の位置を超えた 場合、
0を返す。 - 再帰的ケース:
a[i]を残りの和arraySum(a, i + 1)に加える。
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つの 値を処理し、残りは次のコールに任せる。
よくあるミス
- 再帰にはベースケースが必要であり、そうでなければ StackOverflowError が発生する。
- 各呼び出しは必ずベースケースに近づかなければなりません。
あなたも試してみよう
- 各タスクには、TODOを含むメソッドの骨格が与えられます。基本ケースと再帰ケースの両方を書いてください。
- 隠されたHarnessがいくつかの値であなたのメソッドを呼び出し、結果を検査します。
- Check answerを使用して提供されたテストでコードをコンパイルし、結果を確認してください。スタートファイルに表示されているクラスとメソッドのインターフェースを維持してください。
探索
再帰:ベースケース+再帰ケース
基底条件に達するまで分割し、答えを上へ返していきます。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
factorial(int n) を完成させ、再帰を使って n * (n-1) * ... * 1 を返すようにしなさい。n <= 1 に対するベースケースを使います。チェッカーは複数の値でテストします。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
sumTo(int n) を完成させ、再帰を使って 1 + 2 + ... + n を返すようにしなさい。n <= 0 に対するベースケースを使います。チェッカーは複数の値でテストします。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
arraySum(int[] a, int i)を完成させて、a[i]から終端までの和を返すようにし、再帰を用いて実装してください。ベースケース:iが最終位置を超えた場合は、0を返します。チェッカーは複数の配列をテストします。
実行ボタンをクリックして出力を確認してください。