Recursion
재귀는 함수가 자기 자신을 호출해 반복 작업을 표현하는 방식입니다. 큰 문제를 같은 구조의 더 작은 문제로 쪼개고, 충분히 작아졌을 때 직접 답을 내는 종료 조건을 두어 호출 사슬을 끝냅니다. 반복문이 '몇 번 도는가'에 집중한다면, 재귀는 '문제를 어떻게 쪼개는가'에 집중합니다. 트리처럼 깊이를 미리 알 수 없는 자료구조를 다룰 때 특히 자연스럽습니다.
▶아키텍처 다이어그램
🔄 프로세스 다이어그램점선 애니메이션은 데이터 또는 요청의 흐름 방향을 나타냅니다
파일 시스템을 모두 훑어 특정 확장자 파일을 찾으려면 폴더 안의 폴더 안의 폴더까지 끝없이 내려가야 합니다. 몇 단계 깊이인지 미리 알 수 없는 이 구조를 for 루프로 풀려고 하면 '지금 몇 층에 있는지' 직접 추적해야 하고, 중간에 방문해야 할 폴더 목록을 직접 관리해야 합니다. 반복문이 3~4중으로 중첩되기 시작하면 금방 읽기 어려워집니다. 구조가 스스로 자기 자신을 포함하는 경우(폴더 안의 폴더, 댓글 밑의 댓글, 트리 안의 서브트리)에는 반복문의 일자형 사고보다, '같은 작업을 더 작은 부분에 다시 적용한다'는 관점이 훨씬 직관적입니다.
재귀는 수학의 귀납적 정의에서 출발한 오래된 아이디어입니다. 팩토리얼 `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가 더 간결하고, 트리처럼 분기가 있는 구조에서는 직접 재귀를 쓰는 편이 명확합니다.
재귀는 트리나 그래프 탐색, 파일 시스템 순회, DOM 조작, JSON 중첩 처리, 파서 구현, 정렬 알고리즘 같은 곳에서 핵심 도구로 쓰입니다. React의 Fiber 알고리즘, 컴파일러의 AST 순회, 디렉토리 빌드 도구가 모두 재귀 기반입니다. 실무에서 재귀를 쓸 때는 세 가지를 확인하는 습관이 좋습니다. 종료 조건이 반드시 도달하는가, 매 호출마다 문제 크기가 줄어드는가, 예상 깊이가 언어의 스택 제한 안에 들어오는가. 깊은 재귀가 필요한데 스택이 걱정된다면 반복문으로 바꾸거나 명시적인 스택 자료구조를 써서 시뮬레이션할 수 있습니다. 재귀는 '쓸 수 있는가'가 아니라 '이 구조에 어울리는가'로 선택하는 도구입니다.