소개
어떤 문제를 해결하나요
어떤 문제는 자기 자신의 더 작은 버전으로 자연스럽게 설명됩니다. 폴더는 폴더를 담고, 가계도는 더 작은 가계도를 담으며, n! 은 n 곱하기 (n - 1)! 입니다. 재귀를 쓰면 그런 정의를 그대로 따르는 코드를 쓸 수 있습니다.
일상 속 비유
재귀는 줄을 선 사람들이 질문을 뒤로 넘기는 것과 비슷합니다. 6!을 알고 싶은 첫 번째 사람은 뒷사람에게 5!을 묻고 기다립니다. 그 사람은 또 4!을 묻고, 이렇게 계속 이어지다가 1!을 질문받은 사람이 바로 답합니다. 그러면 답이 줄을 따라 앞으로 돌아오고, 사람마다 자기 숫자를 곱해서 넘깁니다.
factorial(6)🙋 첫 번째 사람: 6 × 기다리는 답number * factorial(number - 1)➡️ 뒷사람에게 더 작은 숫자로 같은 질문을 합니다if number <= 1: return 1🛑 마지막 사람은 바로 답합니다: 1720⬅️ 답이 줄을 따라 돌아옵니다: 720재귀 함수는 바로 답할 수 있는 기저 사례에 닿을 때까지 더 작은 입력으로 자기 자신을 호출합니다. 여기서는 factorial(n) = n × factorial(n - 1) 이고 factorial(1) = 1 입니다.
핵심 포인트
if number <= 1: return 1은 기저 사례로, 이것이 없으면 호출이 멈추지 않습니다.return number * factorial(number - 1)은 더 작은 수로 같은 함수를 호출합니다.factorial(6)은factorial(5)를, 그것은factorial(4)를 기다리며factorial(1)까지 내려갑니다.raise ValueError(...)는 기저 사례에 끝내 닿지 못할 음수를 거부합니다.
언제 사용하나요?
- 더 작은 버전으로 정의되는 문제: 트리, 폴더, 중첩 데이터.
- 병합 정렬 같은 분할 정복 알고리즘.
- 호출 스택이 어떻게 동작하는지 배우기.
필요 없는 경우
- 실제 코드의 팩토리얼 같은 단순한 반복: 반복문이나
math.factorial이 더 빠르고 깊이 제한이 없습니다. - 아주 깊은 입력: Python 은 약 1,000번 중첩된 호출에서 RecursionError 로 멈춥니다.
동작 원리 보기
한 단계를 눌러 각 호출을 따라가세요. 새 호출은 콜 스택에 쌓이고, 각 호출은 자신을 부른 곳에 값을 돌려줍니다.
예제 코드
def factorial(number):
if number < 0:
raise ValueError("Factorial is undefined for negative numbers")
if number <= 1:
return 1
return number * factorial(number - 1)
print(factorial(6))
실행 결과
720
코드 설명
number가 0이나 1이면 함수는 곧바로 1을 돌려줍니다. 이것이 재귀가 끝없이 이어지지 않게 막는 기저 사례입니다. 그 밖의 값에서는 number에 factorial(number - 1)을 곱한 값을 돌려줍니다. 재귀 호출은 호출 스택(call stack)에 하나씩 쌓이므로 재귀 깊이는 O(n)입니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.
- 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
- 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
- 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
자주 하는 실수
기저 사례를 잊기
Python 이 RecursionError 를 일으킬 때까지 함수가 자기 자신을 끝없이 호출합니다.
def factorial(number):
return number * factorial(number - 1)
def factorial(number):
if number <= 1:
return 1
return number * factorial(number - 1)
이 레슨을 마쳤나요?
학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
모든 챌린지