프로그래밍을 처음 배우는 분들이 반복문(For, While)까지는 수월하게 이해하다가, 처음으로 좌절감을 맛보는 구간이 바로 재귀 함수(Recursion)입니다. "함수가 자기 자신을 호출한다니, 이게 무슨 말장난인가?"라는 생각이 들기 십상입니다. 마치 영화 <인셉션>의 꿈속의 꿈처럼, 혹은 두 개의 거울 사이에 섰을 때 무한히 반사되는 내 모습처럼 느껴지기도 합니다.
하지만 재귀 함수는 단순히 '신기한 기법'이 아닙니다. 복잡한 문제를 매우 간결한 코드로 해결할 수 있게 해주는 강력한 도구이며, 추후 배우게 될 트리(Tree), 그래프(Graph), 동적 계획법(DP) 등의 고급 알고리즘을 이해하기 위한 필수 관문입니다. 오늘은 재귀 함수의 핵심 원리와 반드시 지켜야 할 규칙들을 그림을 그리듯 아주 쉽게 설명해 드리겠습니다.
1. 재귀(Recursion)의 핵심 개념: 자기 자신을 호출하다
재귀 함수란, 함수 내부에서 다시 자기 자신을 부르는 함수를 의미합니다. 러시아의 전통 인형인 '마트료시카'를 떠올려 보세요. 인형을 열면 더 작은 인형이 나오고, 그 인형을 열면 또 더 작은 인형이 나옵니다. 이 과정은 가장 작은 인형이 나올 때까지 계속됩니다.
프로그래밍적으로 보면, 큰 문제를 해결하기 위해 그 문제를 더 작은 단위의 동일한 문제로 쪼개어 들어가는 과정입니다. 반복문으로 해결할 수 있는 모든 문제는 재귀 함수로도 구현할 수 있으며, 그 반대도 가능합니다. 하지만 재귀를 사용하면 코드가 훨씬 더 직관적이고 우아해지는 경우가 많습니다.
2. 재귀 함수의 필수 2요소: 종료 조건과 재귀 호출
재귀 함수를 작성할 때 가장 중요한 것은 "언제 멈출 것인가?"입니다. 브레이크 없는 자동차가 위험하듯, 멈추지 않는 재귀 함수는 시스템을 파괴합니다. 재귀 함수는 반드시 다음 두 가지 부분으로 구성되어야 합니다.
2-1. 기저 조건 (Base Case, 종료 조건)
더 이상 자기 자신을 호출하지 않고, 값을 반환하며 빠져나오는 조건입니다. 마트료시카 인형에서 더 이상 열리지 않는 마지막 인형에 해당합니다. 이 조건이 없으면 함수는 무한 루프에 빠지게 되며, 결국 메모리가 꽉 차서 프로그램이 강제 종료되는 스택 오버플로우(Stack Overflow) 오류를 발생시킵니다.
2-2. 재귀 단계 (Recursive Case)
문제를 더 작은 단위로 쪼개며 자기 자신을 호출하는 부분입니다. 이때 전달되는 인자(Parameter)는 반드시 종료 조건(Base Case)을 향해 수렴해야 합니다. 예를 들어 숫자를 1씩 줄여가며 호출하다가, 0이 되면 멈추는 식입니다.
3. 스택 메모리로 보는 재귀의 동작 과정 (팩토리얼 예시)
가장 고전적인 예제인 팩토리얼($3! = 3 \times 2 \times 1$)을 계산하는 과정을 메모리 관점에서 살펴보겠습니다. 컴퓨터는 함수를 호출할 때마다 스택(Stack)이라는 메모리 공간에 작업 명세서(스택 프레임)를 쌓아 올립니다.
- `factorial(3)` 호출: 아직 답을 모릅니다. `3 * factorial(2)`를 계산하기 위해 `factorial(2)`를 호출하고 대기합니다. (스택에 쌓임)
- `factorial(2)` 호출: 아직 답을 모릅니다. `2 * factorial(1)`을 계산하기 위해 `factorial(1)`을 호출하고 대기합니다. (스택에 쌓임)
- `factorial(1)` 호출: 종료 조건 도달! 1을 반환합니다.
- 역순 복귀:
- `factorial(1)`이 1을 반환했으므로, `factorial(2)`는 $2 \times 1 = 2$를 계산하고 반환합니다.
- `factorial(2)`가 2를 반환했으므로, `factorial(3)`은 $3 \times 2 = 6$을 계산하고 최종 반환합니다.
이처럼 재귀는 '들어갔다가(Push) 다시 나오는(Pop)' 과정을 거치게 됩니다.
4. 재귀 함수의 장단점 (Trade-off)
재귀가 항상 좋은 것은 아닙니다. 상황에 맞춰 현명하게 사용해야 합니다.
- 장점: 코드가 간결하고 가독성이 좋아집니다. 변수 사용을 줄일 수 있어 코드의 상태 관리가 쉬워집니다. 특히 트리 탐색이나 퀵 정렬, 하노이의 탑 같은 문제에서 위력을 발휘합니다.
- 단점: 함수 호출은 비용이 꽤 비쌉니다. 호출할 때마다 메모리(스택)를 사용하므로 반복문(For loop)에 비해 메모리를 많이 차지하고 속도가 느릴 수 있습니다. 깊이가 너무 깊어지면 스택 오버플로우 위험이 있습니다.
1. 재귀 함수는 자기 자신을 호출하여 문제를 더 작은 단위로 쪼개 해결하는 방식입니다.
2. 반드시 무한 루프를 방지할 종료 조건(Base Case)이 존재해야 합니다.
3. 코드는 간결해지지만 메모리(스택) 사용량이 늘어나므로, 상황에 따라 반복문과 비교하여 선택해야 합니다.