Recursion
재귀는 함수가 자기 자신을 다시 부르면서 반복 작업을 표현하는 방식입니다. 큰 문제를 같은 모양의 더 작은 문제로 줄여 가고, 충분히 작아졌을 때는 바로 답을 내는 종료 조건에서 멈춥니다. 반복문이 '몇 번 돌까'를 세는 쪽에 가깝다면, 재귀는 '이 문제를 어떻게 더 작은 같은 문제로 바꿀까'를 생각하게 만듭니다. 트리처럼 깊이를 미리 알 수 없는 구조에서 특히 자연스럽습니다.
▶아키텍처 다이어그램
🔄 프로세스 다이어그램Diagram preview
The interactive diagram loads after the page becomes ready.
점선 애니메이션은 데이터 또는 요청의 흐름 방향을 나타냅니다
폴더 안의 폴더를 따라 내려가거나, 댓글 밑의 댓글을 순회하거나, 트리 안의 서브트리를 처리하는 문제를 만나면 깊이가 몇 단계일지 미리 알 수 없습니다. 이런 구조를 for 루프로만 풀려고 하면 지금 몇 층에 있는지, 다음에 어디로 갈지, 방문할 목록이 무엇인지까지 직접 관리해야 해서 코드가 금방 무거워집니다. 중첩이 몇 단계만 깊어져도 반복문은 읽기 힘들어지고, 구조의 핵심보다 제어 흐름이 앞에 튀어나옵니다. 이럴 때는 '같은 작업을 더 작은 부분에 다시 적용한다'는 재귀 관점이 오히려 더 단순합니다.
재귀는 수학의 귀납적 정의에서 출발한 오래된 아이디어입니다. 팩토리얼 n! = n × (n-1)!이나 피보나치 수열처럼 '자기 자신을 참조해 정의되는' 개념을 프로그램으로 옮긴 것이 재귀 함수입니다. Lisp를 비롯한 초기 함수형 언어는 반복문 자체가 없고 모든 반복을 재귀로 표현했습니다. 오늘날 명령형 언어에서도 재귀는 트리 순회, 파서, 그래프 알고리즘의 기본 도구로 자리 잡고 있습니다. 다만 호출 스택 깊이 제한 때문에 매우 깊은 재귀는 언어에 따라 제한이 있고, 이를 해결하기 위한 꼬리 재귀 최적화(tail call optimization) 같은 기법도 함수형 언어를 중심으로 발전했습니다.
재귀 함수를 설계할 때는 두 가지 부분을 분리해서 생각합니다. 첫째는 종료 조건입니다. 더 이상 쪼갤 필요가 없거나 쪼갤 수 없는 가장 단순한 상태에서 바로 답을 반환합니다. 빈 배열이면 0을 반환, 빈 트리면 null 반환, 1이면 1 반환 같은 식입니다. 둘째는 재귀 단계입니다. 현재 문제를 한 단계 더 작은 같은 형태의 문제로 줄이고, 그것을 자기 자신을 호출해 푼 뒤 현재 단계의 결과와 결합합니다. 호출할 때마다 호출 스택에 새 프레임이 쌓이고, 종료 조건에 도달하면 거꾸로 결과가 조립되며 풀려 나옵니다. 종료 조건을 빼먹으면 스택 오버플로우, 축소 방향을 잘못 잡으면 무한 재귀가 됩니다.
중첩 배열 평탄화
// 깊이를 모르는 중첩 배열을 1차원으로 펼치기
function flatten(arr) {
// 종료 조건: 빈 배열이면 빈 배열
if (arr.length === 0) return [];
const [head, ...tail] = arr;
// head가 배열이면 재귀적으로 펼치고, 아니면 그대로 씀
const headFlat = Array.isArray(head) ? flatten(head) : [head];
// 나머지(tail)도 재귀적으로 펼쳐서 합침
return [...headFlat, ...flatten(tail)];
}
flatten([1, [2, [3, [4, 5]]], 6]); // [1, 2, 3, 4, 5, 6]
// 트리 순회도 같은 패턴
function countNodes(tree) {
if (tree === null) return 0; // 종료 조건
return 1 + countNodes(tree.left) + countNodes(tree.right); // 재귀
}flatten은 첫 원소가 배열이면 재귀적으로 펼치고, 나머지도 재귀적으로 처리합니다. countNodes는 '현재 노드 1개 + 왼쪽 서브트리 개수 + 오른쪽 서브트리 개수'로 자기 자신을 정의합니다. 두 함수 모두 '종료 조건 → 더 작은 문제로 줄이기' 패턴을 따릅니다.
재귀와 반복문은 둘 다 같은 작업을 여러 번 수행하지만 사고방식이 다릅니다. 반복문은 '카운터를 올리며 몇 번 돈다'는 시간축 관점이고, 재귀는 '문제를 같은 구조의 작은 문제로 쪼갠다'는 구조적 관점입니다. 선형 자료구조(배열, 숫자 범위)는 반복문이 보통 더 직관적이고 성능도 약간 유리합니다. 트리, 그래프, 중첩 구조처럼 데이터 자체가 재귀적으로 정의되는 경우에는 재귀가 훨씬 자연스럽습니다. 같은 문제를 두 방식으로 풀 수 있을 때는 '이 문제를 설명하는 가장 자연스러운 말이 무엇인가'를 기준으로 고르면 됩니다. 재귀와 reduce도 겹치는 면이 있습니다. reduce는 사실 배열에 대한 재귀 패턴을 일반화한 도구입니다. 배열이나 선형 시퀀스를 누적하는 작업이라면 reduce가 더 간결하고, 트리처럼 분기가 있는 구조에서는 직접 재귀를 쓰는 편이 명확합니다.
Gain 문제의 구조를 코드에 그대로 옮길 수 있어 트리와 중첩 데이터처럼 자기 닮은 구조를 설명하고 구현하기 쉬워집니다. Cost 호출마다 스택 프레임이 쌓이므로 입력이 깊어지면 오버플로우 위험이 있고, 호출이 여러 갈래로 퍼지는 재귀는 성능과 디버깅 난도가 빠르게 올라갑니다. Decision Scale 깊이를 미리 모르거나 데이터 자체가 재귀적으로 생긴 경우에는 재귀가 가장 자연스럽습니다. 반대로 선형 배열처럼 반복문이나 reduce로 더 단순하게 표현되는 구조라면 굳이 재귀를 택할 이유가 적습니다.
재귀는 트리·그래프 탐색, 파일 시스템 순회, DOM 조작, 중첩 JSON 처리, 파서, 정렬 알고리즘처럼 구조가 자기 자신을 품고 있는 문제에서 핵심 도구가 됩니다. 컴파일러의 AST 순회나 디렉토리 빌드 도구도 같은 패턴 위에 서 있습니다. 실무에서는 종료 조건이 반드시 도달하는지, 호출할수록 문제가 실제로 작아지는지, 예상 깊이가 스택 한도를 넘지 않는지를 먼저 점검하는 습관이 중요합니다. 깊이가 너무 깊다면 반복문이나 명시적 스택으로 바꾸는 편이 더 안전할 수 있습니다.