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.
한국어
자신을 호출하는 함수
- **재귀(recursion)**란 함수가 자신을 호출하는 것입니다.
- 각 호출은 문제의 더 작은 버전에서 작동해야 합니다.
- 올바르게 구현되면 문제가 작아져서 해결하기 쉬워집니다.
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).
한국어
기본 경우와 재귀 경우
- **기본 경우(base case)**는 가장 간단한 경우로, 재귀를 멈춥니다.
- **재귀 경우(recursive case)**는 더 작은 입력에 대해 함수를 다시 호출합니다.
- 기본 경우가 없으면 함수가 멈추지 않습니다(오류 발생).
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.
한국어
풀이 예제: 계승(factorial)
- 계승
n!는n × (n-1) × ... × 1를 의미합니다. - 재귀 형태로:
n! = n × (n-1)!이며, 기본 경우는0! = 1입니다. - 각 호출은
n를 한 단계 낮은 계승 값과 곱합니다.
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.
한국어
컴퓨터가 실행하는 방식
- 각 호출은 내부 호출이 완료될 때까지 **호출 스택(call stack)**에서 일시 정지됩니다.
- 기본 경우가 반환되면 일시 정지된 호출들이 하나씩 완료됩니다.
- 호출이 너무 많으면 스택 오버플로우가 발생하여 Python이
RecursionError오류를 raised합니다.
English
In Cambridge pseudocode
- A recursive function names its base case and recursive case clearly.
한국어
캐미지아 가위코드에서
- 재귀 함수는 기본 경우와 재귀 cases를 명확하게 명명합니다.
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.
한국어
이제 직접 해보기
- 각 함수에 기본 경우와 재귀 경우를 제공하십시오.
- Answer 확인 버튼을 눌러 코드를 테스트하세요.
Explore · 탐색하기
Recursion returns from the leaves · 재귀는 잎(node)에서返回值
Each call splits into smaller calls; answers return up from the base cases. · 매번 호출이 더 작은 호출로 분지되며, 결과값은 기본ケース(base cases)에서 위로 올라와返回합니다.
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을 반환하세요. 기본 CASE는 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승을 반환하세요. 기본 CASE는 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]을 반환하세요. 기본 CASE는 count_up(0)이며, 이는 빈列表 []입니다.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.