| English | 意味 |
|---|---|
| Recursion/rɪˈkɜːʃn/ | 再帰 |
| base case/beɪs keɪs/ | ベースケース |
| recursive case/rɪˈkɜːsɪv keɪs/ | 再帰ケース |
| unwind/ʌnˈwaɪnd/ | アンワインド |
自身を呼び出す方法
- 再帰とは、同じ問題のより小さな版を解くために自身が自身を呼び出すことである。
- どの再帰にも2つの部分が必要：ベースケースと再帰ケース。
- ベースケースは再帰を停止させる — 小さな入力に対して直接回答する条件。
- 再帰ケースは、より小さい入力で自身を再び呼び出す。
ベースケース
- ベースケースがないと、方法は永遠に自身を呼び出し続け、
StackOverflowErrorが発生する。 - ベースケースは、別の呼び出しなしに最小の入力を処理する。
- 例：
factorial(0)は1を直接返す — これ以上呼び出さない。 - 常に確認すること：すべての経路が最終的にベースケースに到達するか？
再帰ケース
- 再帰ケースは少し処理を行い、その後より小さい入力で自身を呼び出す。
factorial(n)はn * factorial(n - 1)を返す — 呼び出しごとに入力が1つずつ減少する。- 各呼び出しは、より小さい呼び出しが返ってくるまで待機する。
- 呼び出しがスタックに積まれ、ベースケースに達すると、**逆順に展開（unwind）**してトップに戻る。
呼び出しのスタック構造
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)は1を返す；次にスタックが展開される：1, 1, 2, 6。- 各呼び出しは、返るまで自身のパラメータのコピーを保持する。
- 再帰をトレースするとは、呼び出しを下方向にたどり、その後、返り値を上方向にたどることである。
すべての再帰にはそれを停止するベースケースが必要であり、各再帰呼び出しは必ずそのベースケースへ向かう（より小さい入力でなければならない）。 ベースケースを見落としたり、同じ入力や大きい入力で呼び出したりすると、StackOverflowError になるまで無限に再帰し続ける。トレースするには、呼び出しを下方向にたどってベースケースに到達させ、その後、返り値を上方向にたどる。
sum(n) = 1 + 2 + … + n の再帰による計算:
- ベースケース:
if (n == 0) return 0; - 再帰ケース:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
再帰とは、より小さい入力で自身が自身を呼び出すことである。ベースケース（直接停止し、それ以上呼び出さない）と再帰ケース（少し処理を行い、より小さい入力で再帰する）が必要である。呼び出しはベースケースまでスタックされ、その後逆順に展開して戻る。ベースケースを見落とすとStackOverflowError 发生する。
factorial(3) は基底ケースから展開される
fact(0) は 1 を返す（基底ケース）；各親関数は乗算する: 1, 1, 2, 6。
再帰メソッドとは、...であるメソッドのこと
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
再帰 = メソッド自身が自身を呼び出すこと。
基底ケースとは...
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
基底ケースは再帰を停止させる。
到達可能な基底ケースのない再帰は...を引き起こす
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
スタックが溢れるまで無限に再帰する。
再帰ケースは常に自身を...に対して呼び出す必要がある
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
各呼び出しは基底ケースに向かって縮小する必要がある。
factorial(0)=1 および factorial(n)=n*factorial(n-1) のとき、factorial(3) はいくつか？
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
3 * 2 * 1 * 1 = 6.
各再帰呼び出しは、返還するまで自身の参数の独自のコピーを保持する。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
呼び出しは独立して実行され、その後展開される。