このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
自身を呼び出す関数
- 再帰とは、関数が自分自身を呼び出すことです。
- 各呼び出しでは問題のより小さいバージョンを扱います。
- 適切に行えば、問題は縮小して解くのが単純になります。
ベースケースと再帰ケース
- ベースケースは最も単純なケースであり、これにより再帰が停止します。
- 再帰ケースは、より小さい入力に対して関数を再度呼び出します。
- ベースケースがないと関数は止まらず(エラーになります)。
English
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
計算例:階乗
- 階乗
n!とはn × (n-1) × ... × 1を意味します。 - 再帰形式では
n! = n × (n-1)!、ベースケースは0! = 1です。 - 各呼び出しは
nを1つ少ない値の階乗に乗算します。
English
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
コンピュータによる実行方法
- 各呼び出しは内部の呼び出しを待つ間にコールスタック上で一時停止されます。
- ベースケースが返されると、一時停止された呼び出しが1つずつ完了します。
- 呼び出しが多すぎるとスタックオーバーフローが発生し、Pythonは
RecursionErrorをraiseします。
Cambridge擬似コードにおける表現
- 再帰関数はベースケースと再帰ケースを明確に名付けます。
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
よくあるミス
- 全ての再帰にはベースケースが必要で、そうでなければコールスタックがオーバーフローします。
- 各呼び出しは必ずベースケースに近づかなければなりません。
あなたも試してみよう
- 各関数にベースケースと再帰ケースを与えてください。
- 回答を確認 を押してコードを試してください。
探索
再帰は葉ノードから戻ってくる
各呼び出しはより小さな呼び出しに分割され、答えは基本ケースから上方へreturnされる。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
sum_to(n) という再帰関数を記述し、1 + 2 + ... + n を返回する。基本ケースは sum_to(0) で、その値は 0 である。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
power(base, exp) という再帰関数を記述し、base の exp 乗を返回する。基本ケースは exp == 0 で、その結果は 1 である。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
count_up(n) という再帰関数を記述し、リスト [1, 2, ..., n] を返回する。基本ケースは count_up(0) で、それは空のリスト [] である。
実行ボタンをクリックして出力を確認してください。