프로그래밍을 처음 배울 때 반복문(for, while)까지는 수월하게 이해하다가, 처음으로 벽을 느끼는 구간이 바로 재귀 함수(Recursion)입니다. "함수가 자기 자신을 호출한다니, 이게 무슨 말장난인가?"라는 생각이 들기 십상입니다. 하지만 재귀는 복잡한 문제를 매우 간결하고 우아하게 해결할 수 있는 강력한 도구입니다. 특히 DFS(깊이 우선 탐색), 트리 순회, 동적 계획법 등 고급 알고리즘의 기초가 되므로 반드시 정복해야 합니다. 오늘은 재귀 함수의 동작 원리를 그림을 그리듯 쉽게 설명해 드립니다.
1. 재귀의 정의: 마트료시카 인형
[Image of Recursion call stack diagram]
재귀 함수는 함수 내부에서 다시 자기 자신을 부르는 함수입니다. 가장 좋은 비유는 러시아 인형 '마트료시카'입니다. 인형을 열면 더 작은 인형이 나오고, 그 인형을 열면 또 더 작은 인형이 나옵니다. 이 과정은 가장 작은 인형이 나올 때까지 계속됩니다. 프로그래밍적으로는 큰 문제를 해결하기 위해 그 문제를 더 작은 단위의 동일한 문제로 쪼개어 들어가는 과정입니다.
2. 재귀 함수의 필수 2요소
재귀 함수를 작성할 때 가장 중요한 것은 "언제 멈출 것인가?"입니다. 브레이크 없는 자동차가 위험하듯, 멈추지 않는 재귀 함수는 시스템을 파괴합니다. 따라서 반드시 다음 두 가지 부분으로 구성되어야 합니다.
2-1. 기저 조건 (Base Case)
더 이상 자기 자신을 호출하지 않고, 값을 반환하며 빠져나오는 종료 조건입니다. 마트료시카의 마지막 인형에 해당합니다. 이 조건이 없으면 함수는 무한 루프에 빠지게 되며, 결국 메모리가 꽉 차서 프로그램이 강제 종료되는 스택 오버플로우(Stack Overflow) 오류를 발생시킵니다.
2-2. 재귀 단계 (Recursive Case)
문제를 더 작은 단위로 쪼개며 자기 자신을 호출하는 부분입니다. 이때 전달되는 인자(Parameter)는 반드시 종료 조건(Base Case)을 향해 수렴해야 합니다. 예를 들어 `n`을 호출했다면 다음엔 `n-1`을 호출하여 언젠가는 0이 되도록 만들어야 합니다.
3. 팩토리얼(Factorial)로 보는 재귀의 흐름
$5! = 5 \times 4 \times 3 \times 2 \times 1$을 구하는 과정을 코드로 보면 다음과 같습니다.
function factorial(n) {
if (n === 1) return 1; // 기저 조건 (1이 되면 멈춤)
return n * factorial(n - 1); // 재귀 단계
}
1. `factorial(3)`은 `3 * factorial(2)`를 호출하고 대기합니다. (스택에 쌓임) 2. `factorial(2)`는 `2 * factorial(1)`을 호출하고 대기합니다. (스택에 쌓임) 3. `factorial(1)`은 종료 조건을 만나 `1`을 반환합니다. 4. 이제 역순으로 계산이 시작됩니다. `2 * 1 = 2`, `3 * 2 = 6`... 이처럼 재귀는 "들어갔다가(Push) -> 일을 처리하고 -> 다시 나오는(Pop)" 스택 구조를 가집니다.
1. 재귀 함수는 자기 자신을 호출하여 문제를 더 작은 단위로 쪼개 해결하는 방식입니다.
2. 무한 루프를 방지하기 위해 반드시 종료 조건(Base Case)이 존재해야 합니다.
3. 코드는 간결해지지만, 호출 깊이가 깊어지면 스택 오버플로우가 발생할 수 있어 주의가 필요합니다.