Recursion · 再帰
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.
- Each call should work on a smaller version of the problem.
- Done right, the problem shrinks until it is trivial to solve.
日本語
自身を呼び出す関数
- 再帰とは、関数が自分自身を呼び出すことです。
- 各呼び出しでは問題のより小さいバージョンを扱います。
- 適切に行えば、問題は縮小して解くのが単純になります。
English
Base case and recursive case
- The base case is the simplest case — it stops the recursion.
- The recursive case calls the function again on a smaller input.
- Without a base case the function never stops (an error).
日本語
ベースケースと再帰ケース
- ベースケースは最も単純なケースであり、これにより再帰が停止します。
- 再帰ケースは、より小さい入力に対して関数を再度呼び出します。
- ベースケースがないと関数は止まらず（エラーになります）。
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
English
A worked example: factorial
- The factorial
n!meansn × (n-1) × ... × 1. - In recursive form:
n! = n × (n-1)!, and the base case is0! = 1. - Each call multiplies
nby the factorial of one less.
日本語
計算例：階乗
- 階乗
n!とはn × (n-1) × ... × 1を意味します。 - 再帰形式では
n! = n × (n-1)!、ベースケースは0! = 1です。 - 各呼び出しは
nを1つ少ない値の階乗に乗算します。
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
English
How the computer runs it
- Each call is paused on a call stack while it waits for the inner call.
- When the base case returns, the paused calls finish one by one.
- Too many calls overflow the stack — Python raises a
RecursionError.
日本語
コンピュータによる実行方法
- 各呼び出しは内部の呼び出しを待つ間にコールスタック上で一時停止されます。
- ベースケースが返されると、一時停止された呼び出しが1つずつ完了します。
- 呼び出しが多すぎるとスタックオーバーフローが発生し、Pythonは
RecursionErrorをraiseします。
English
In Cambridge pseudocode
- A recursive function names its base case and recursive case clearly.
日本語
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
English
Common mistakes
- Every recursion needs a base case, or it overflows the call stack.
- Each call must move closer to the base case.
日本語
よくあるミス
- 全ての再帰にはベースケースが必要で、そうでなければコールスタックがオーバーフローします。
- 各呼び出しは必ずベースケースに近づかなければなりません。
English
Now you try
- Give each function a base case and a recursive case.
- Press Check answer to test your code.
日本語
あなたも試してみよう
- 各関数にベースケースと再帰ケースを与えてください。
- 回答を確認 を押してコードを試してください。
Explore · 探索
Recursion returns from the leaves · 再帰は葉ノードから戻ってくる
Each call splits into smaller calls; answers return up from the base cases. · 各呼び出しはより小さな呼び出しに分割され、答えは基本ケースから上方へreturnされる。
Write a recursive sum_to(n) that returns 1 + 2 + ... + n. The base case is sum_to(0) which is 0. · sum_to(n) という再帰関数を記述し、1 + 2 + ... + n を返回する。基本ケースは sum_to(0) で、その値は 0 である。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Write a recursive power(base, exp) that returns base raised to exp. The base case is exp == 0, which gives 1. · power(base, exp) という再帰関数を記述し、base の exp 乗を返回する。基本ケースは exp == 0 で、その結果は 1 である。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Write a recursive count_up(n) that returns the list [1, 2, ..., n]. The base case is count_up(0) which is the empty list []. · count_up(n) という再帰関数を記述し、リスト [1, 2, ..., n] を返回する。基本ケースは count_up(0) で、それは空のリスト [] である。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。