10 — 재귀 개념

람다가 마주 본 거울(또는 마트료시카 인형) 속에 거울이 또 들어 있는 것을 보며 "자기 안에 자기가 또 있네?"라고 발견하고, 제네릭이 "그럼 끝없이 들어가?"라고 묻자 돌핀쌤이 "맞아요, 그게 바로 재귀예요. 단, 멈추는 조건이 꼭 있어야 해요"라고 안내하는 도입

🙋‍♀️ 람다: "선생님, 마주 본 거울을 봤는데 거울 안에 거울이 있고, 그 안에 또 거울이 있고… 끝없이 자기 안에 자기가 들어 있었어요!"

🐬 돌핀쌤: "두 친구가 오늘 배울 걸 미리 발견했네요! 함수가 자기 자신을 또 부르는 것을 재귀라고 해요. 단, 거울과 다르게 재귀는 반드시 어딘가에서 멈춰야 한답니다. 천천히 함께 알아봐요."

🎯 오늘 완성할 코드는?

오늘 우리가 만들 건 재귀로 만든 카운트다운이에요. 3, 2, 1, 발사! 처럼 숫자를 하나씩 줄여 가며 외치고, 정해진 곳에서 딱 멈추는 코드예요.

먼저 완성된 모습부터 볼게요. 지금은 이해 안 돼도 괜찮아요. 아래에서 한 줄씩 천천히 뜯어볼 거예요.

def countdown(n):
    if n <= 0:             # base case — 여기서 멈춤
        print("발사!")
        return
    print(n)
    countdown(n - 1)       # 재귀 호출 — n을 줄여서 호출

countdown(3)

실행하면 이렇게 나와요.

3
2
1
발사!

countdown 함수가 자기 자신을 또 부르면서 3 → 2 → 1 로 내려가다가, 0 이 되는 순간 발사! 를 외치고 멈췄죠?

🐬 돌핀쌤: "몇 줄 안 되는 짧은 코드지만, 이 안에 재귀의 핵심이 다 들어 있어요. 함수가 자기를 부르는 것, 그리고 멈추는 조건이요. 지금부터 이 코드가 왜 잘 멈추는지 하나씩 풀어볼게요."

💡 어떻게 풀까? — 멈추는 조건이 있는 거울

마주 본 거울 안에 거울이 끝없이 반복되는 모습으로 '함수가 자기 자신을 호출'하는 재귀 비유

람다가 본 거울을 다시 떠올려 봐요. 거울 두 개를 마주 보게 세우면 거울 안에 거울이 보이고, 그 안에 또 거울이 보여요.

[거울] → 안에 [거울] → 안에 [거울] → 안에 [거울] → ...

재귀도 이와 똑같아요. 함수 안에서 같은 함수를 또 부르는 거예요.

그런데 거울은 영원히 반복되지만, 코드가 영원히 반복되면 큰일 나요. 만약 멈추는 조건 없이 이렇게만 쓰면요.

def countdown(n):
    print(n)
    countdown(n - 1)   # 자기 자신을 호출 (멈추는 조건이 없음!)

3, 2, 1, 0, -1, -2 … 끝없이 내려가다가 결국 파이썬이 RecursionError(너무 깊이 들어갔어요!) 를 내고 멈춰버려요.

🙋‍♂️ 제네릭: "아하, 그래서 거울처럼 끝없이 가면 안 되고 **'여기서 그만!' 하는 줄'**이 필요한 거군요."

그 '여기서 그만!' 선이 바로 맨 위 코드의 if n <= 0: 이에요. 이걸 base case(종료 조건) 라고 불러요.

🔍 코드 한 줄씩 뜯어보기

이제 맨 위에서 본 완성 코드를 한 줄씩 볼게요.

① 멈추는 조건 — base case

    if n <= 0:             # base case — 여기서 멈춤
        print("발사!")
        return

n 이 0 이하가 되면 더 내려가지 않고 발사! 를 외친 뒤 return 으로 멈춰요. 재귀에는 이렇게 멈추는 줄이 반드시 있어야 해요.

💡 n == 0 이 아니라 n <= 0 으로 넉넉하게 잡은 이유: 혹시 n 이 0을 살짝 건너뛰어 음수로 내려가도 멈추게 하려는 안전한 습관이에요.

② 지금 숫자를 외쳐요

    print(n)

base case가 아니면(아직 멈출 때가 아니면) 지금 n 값을 출력해요. countdown(3) 이면 먼저 3 을 외쳐요.

③ 자기 자신을 다시 불러요 — 단, 더 작게!

    countdown(n - 1)       # 재귀 호출 — n을 줄여서 호출

여기가 재귀의 핵심이에요. countdown 이 자기 자신을 다시 부르는데, n 그대로가 아니라 n - 1 로 한 칸 줄여서 불러요. 매번 1씩 작아지니까 결국 base case(n <= 0)에 반드시 도착해요.

💡 만약 countdown(n - 1) 이 아니라 countdown(n) 이었다면? 숫자가 줄지 않으니 영원히 같은 값으로 자기를 부르며 멈추지 못해요. 재귀 호출은 매번 base case에 가까워져야 해요.

④ 호출이 쌓였다가 되돌아와요 — call stack

함수가 자기를 부르면, 부른 쪽은 "이게 끝날 때까지 기다려야 해" 하고 잠깐 멈춰서 기다려요. 이렇게 기다리는 함수들이 차곡차곡 쌓이는 것을 call stack(호출 스택) 이라고 해요.

countdown(3)이 0까지 차곡차곡 쌓였다가 base case에서 위부터 하나씩 빠지며 되돌아오는 call stack

countdown(3) 호출 → 3 출력 → countdown(2) 부르고 대기
  countdown(2) 호출 → 2 출력 → countdown(1) 부르고 대기
    countdown(1) 호출 → 1 출력 → countdown(0) 부르고 대기
      countdown(0) → base case! "발사!" 출력하고 return ↑
    countdown(1) 도 끝 → return ↑
  countdown(2) 도 끝 → return ↑
countdown(3) 도 끝 → return ↑  (스택이 다 비워짐)

마치 접시를 차곡차곡 쌓았다가, 맨 위(가장 마지막에 부른 countdown(0))부터 하나씩 꺼내는 것과 같아요.

⑤ 전체가 어떻게 굴러가는지 — countdown(3)

countdown(3) → "3" 출력
countdown(2) → "2" 출력
countdown(1) → "1" 출력
countdown(0) → n <= 0 이므로 "발사!" 출력하고 멈춤

🙋‍♀️ 람다: "숫자를 하나씩 줄이며 자기를 부르다가, 0이 되는 순간 딱 멈추네요! base case가 있으니까 안심이에요."

✍️ 직접 완성해보기

이제 빈칸을 채워 직접 완성해봐요. 위에서 본 그대로예요.

def countdown(n):
    if n <= ___:           # base case — 여기서 멈춤
        print("발사!")
        return
    print(n)
    countdown(n - ___)     # 재귀 호출 — n을 줄여서 호출

countdown(3)

🐬 돌핀쌤: "막히면 위 '코드 한 줄씩 뜯어보기'로 다시 올라가서 확인해요. 첫 빈칸은 멈추는 기준 숫자, 둘째 빈칸은 n을 얼마나 줄일지예요. 다 채웠으면 맨 위 🎯 완성 코드와 비교해보세요. 정답을 외우는 게 아니라 왜 그런지 떠올리는 게 진짜 공부예요."

📌 오늘 배운 것

개념	설명
재귀	함수가 자기 자신을 또 부르는 것
base case	재귀를 멈추는 조건 — `if n <= 0:` 처럼 반드시 있어야 함
재귀 호출	`countdown(n - 1)` 처럼 매번 더 작게 만들어 자신을 호출
call stack	기다리는 함수들이 쌓였다가 base case에서 역순으로 돌아옴
무한 재귀	base case가 없거나 문제가 작아지지 않으면 `RecursionError` 발생

재귀를 쓸 땐 항상 이 두 가지를 먼저 확인하세요. ① base case가 있는가? ② 호출마다 문제가 더 작아지는가?

🐬 돌핀쌤: "자기 자신을 부르기, 멈추는 조건, 그리고 쌓였다 되돌아오기! 이 세 박자만 기억하면 재귀가 하나도 안 무서워요. 잘했어요! 👏"

▸ 더 해보기 — 여기서부터는 선택!

돌핀쌤이 칠판 앞에서 지느러미로 손가락을 펴며 재귀의 핵심(① 함수가 자기 자신 호출 ② base case 필수 ③ call stack은 쌓였다 역순으로 돌아옴)을 정리하고 람다·제네릭이 끄덕이는 장면

여기까지가 오늘의 필수 내용이에요. 아래는 여유 있을 때 도전하는 내용이고, 예제 문제로 직접 풀어볼 수 있어요. 외울 필요는 없어요. 전부 오늘 배운 'base case + 더 작게 호출'이라는 같은 뼈대 위에 살을 붙인 거예요.

팩토리얼(factorial) — 5! = 5 × 4 × 3 × 2 × 1 = 120 처럼 1부터 n까지 곱한 값이에요. 잘 보면 n! = n × (n-1)! 이라 재귀로 딱 맞아요. base case는 n <= 1 → 1, 재귀 호출은 n * factorial(n - 1). → 예제로 연습
거듭제곱(power) — a 를 b 번 곱한 값이에요. power(a, b) = a × power(a, b-1), base case는 b <= 0 → 1. 팩토리얼과 똑같은 모양이에요. → 예제로 연습
1부터 n까지의 합 — sum_recursive(n) = n + sum_recursive(n - 1), base case는 n <= 0 → 0. 같은 문제를 반복문(for)으로도 풀어 보고 재귀와 비교해보세요. → 예제로 연습

참고 — 재귀 vs 반복문

같은 문제를 재귀로도, 반복문(for)으로도 풀 수 있어요. 둘은 이런 차이가 있어요.

비교 항목	반복문	재귀
속도	보통 더 빠름	함수 호출이 쌓여 약간 느림
메모리	적게 사용	call stack 메모리 사용
잘 맞는 경우	단순 반복	트리·분할정복·수학적 정의(팩토리얼 등)

참고 — base case가 없으면 왜 에러가 날까?

파이썬은 재귀를 약 1000번까지만 허용해요. base case가 없으면 호출이 계속 쌓이다가, 그 한계를 넘는 순간 RecursionError: maximum recursion depth exceeded 가 나요.

countdown(3) → countdown(2) → ... → countdown(-994) → 에러!

그래서 재귀를 쓸 때 base case는 빠뜨리면 안 되는 안전장치예요.

10 — 재귀 개념

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1