이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
자신을 호출하는 함수
- **재귀(recursion)**란 함수가 자신을 호출하는 것입니다.
- 각 호출은 문제의 더 작은 버전에서 작동해야 합니다.
- 올바르게 구현되면 문제가 작아져서 해결하기 쉬워집니다.
기본 경우와 재귀 경우
- **기본 경우(base case)**는 가장 간단한 경우로, 재귀를 멈춥니다.
- **재귀 경우(recursive case)**는 더 작은 입력에 대해 함수를 다시 호출합니다.
- 기본 경우가 없으면 함수가 멈추지 않습니다(오류 발생).
English
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
풀이 예제: 계승(factorial)
- 계승
n!는n × (n-1) × ... × 1를 의미합니다. - 재귀 형태로:
n! = n × (n-1)!이며, 기본 경우는0! = 1입니다. - 각 호출은
n를 한 단계 낮은 계승 값과 곱합니다.
English
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
컴퓨터가 실행하는 방식
- 각 호출은 내부 호출이 완료될 때까지 **호출 스택(call stack)**에서 일시 정지됩니다.
- 기본 경우가 반환되면 일시 정지된 호출들이 하나씩 완료됩니다.
- 호출이 너무 많으면 스택 오버플로우가 발생하여 Python이
RecursionError오류를 raised합니다.
캐미지아 가위코드에서
- 재귀 함수는 기본 경우와 재귀 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
흔한 실수
- 모든 재귀에는 기본 경우가 필요하며, 그렇지 않으면 호출 스택이 오버플로우됩니다.
- 각 호출은 반드시 기본 경우에 가까워져야 합니다.
이제 직접 해보기
- 각 함수에 기본 경우와 재귀 경우를 제공하십시오.
- Answer 확인 버튼을 눌러 코드를 테스트하세요.
탐색하기
재귀는 잎에서 시작하여 위로 올라옵니다.
매번 호출이 더 작은 호출로 나뉘며, 답은 기본 경우에서 위로 반환됩니다.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
sum_to(n)을 재귀적으로 작성하여 1 + 2 + ... + n을 반환하세요. 기본 CASE는 sum_to(0)이며, 이 경우의 값은 0입니다.
출력을 보려면 '실행'을 클릭하세요.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
power(base, exp)을 재귀적으로 작성하여 base의 exp승을 반환하세요. 기본 CASE는 exp == 0이며, 이 경우의 값은 1입니다.
출력을 보려면 '실행'을 클릭하세요.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
목록 [1, 2, ..., n]을 반환하는 재귀적 count_up(n)를 작성하십시오. 기본 경우는 count_up(0)이며, 이는 빈 목록 []입니다.
출력을 보려면 '실행'을 클릭하세요.