DISCRETE MATH · CHAPTER 04
중급 · 48분재귀와 귀납적 사고
작은 문제에서 전체 해답까지
재귀의 종료 조건·점화식·수학적 귀납법의 구조를 설명한다.
CONCEPTS
개념을 문장으로 설명하기
기저 사례
재귀 호출을 멈추고 답을 바로 반환하는 가장 작은 문제입니다.
예시
factorial(0)=1을 정하지 않으면 factorial(1)이 끝나지 않습니다.
CHECK기저 사례 누락은 무한 재귀로 이어진다.
재귀 관계
큰 문제의 해답을 더 작은 같은 종류의 문제 해답으로 표현한 규칙입니다.
예시
factorial(n)=n×factorial(n−1)입니다.
CHECK문제 크기가 반드시 기저 사례로 가까워져야 한다.
귀납법
기본 단계가 맞고 n에서 맞다면 n+1에서도 맞음을 보여 모든 자연수에서 성립하게 하는 증명입니다.
예시
반복문 불변식을 증명할 때도 비슷한 사고를 씁니다.
CHECK가정과 증명해야 할 다음 단계를 분리한다.
GUIDED PRACTICE
팩토리얼 호출 추적
factorial(4)를 재귀로 계산합니다.
- 4×factorial(3) → 4×3×factorial(2)로 줄입니다.
- 계속 줄여 factorial(0)=1 기저 사례에 도달합니다.
- 호출이 돌아오며 1, 2, 6, 24를 계산합니다.
결론
재귀는 ‘작은 같은 문제’와 ‘반드시 끝나는 기저 사례’가 함께 있어야 합니다.
ACTIVE RECALL · 4 STEPS
가리고, 말하고, 확인하기
읽기만 하지 말고 답을 떠올린 뒤 펼쳐 보세요.
01 · 정의 회상
“기저 사례”을(를) 보지 않고 한 문장으로 정의해 보세요.
02 · 비교 설명
“재귀 관계”이(가) 필요한 상황을 예시와 함께 설명해 보세요.
03 · 핵심 점검
가정과 증명해야 할 다음 단계를 분리한다.
04 · 풀이 재현
“팩토리얼 호출 추적”의 결론을 보기 전에 풀이 순서를 3단계로 다시 적어 보세요.
WORKBOOK · STEP BY STEP
개념 확인 문제
정답을 고르고 해설로 사고 과정을 확인하세요.
01
재귀 함수에서 반드시 필요한 두 요소는?
02
factorial(0)을 1로 두는 주된 이유는?
03
수학적 귀납법의 기본 단계가 하는 일은?
SPEAK IT OUT
면접 1분 답변 연습
반복문과 재귀의 장단점, 그리고 재귀가 종료하려면 어떤 조건이 필요한지 설명해 보세요.
답변할 때는 정의 → 이유 → 짧은 예시 순서로 말해 보세요.공식·표준 자료로 더 읽기
Python docs · Recursion limit원문 열기 ↗실제 언어 런타임에서 재귀 깊이가 왜 제한되는지 확인합니다.