재귀는 흔히 “어렵다”, “면접용 개념이다” 라고 생각하기 쉽다.
하지만 알고 보면 우리는 이미 자바스크립트 곳곳에서
재귀를 자연스럽게 사용하고 있다.
이미 사용 중인 재귀의 예
1️⃣ JSON.parse / JSON.stringify
중첩된 객체나 배열을 처리할 때
내부적으로 재귀 구조를 사용한다.
const obj = {
a: 1,
b: { c: 2, d: { e: 3 } }
};이처럼 객체 안에 객체가 계속 들어가는 구조를 처리하려면
“같은 작업을 반복적으로 수행”해야 한다.
이때 가장 자연스러운 방식이 재귀다.
2️⃣ DOM 트리 탐색
document.getElementById("app")DOM 자체는 트리 구조다.
- 부모 노드
- 자식 노드
- 그 아래 또 자식 노드…
특정 노드를 찾으려면
트리를 타고 계속 내려가야 한다.
이런 구조는 반복문보다
재귀가 훨씬 자연스럽다.
3️⃣ 중첩 객체 순회
{
user: {
profile: {
name: "John"
}
}
}중첩 객체를 끝까지 순회하려면
“객체 안에 객체가 있으면 다시 순회”해야 한다.
이 패턴이 바로 재귀다.
재귀란 무엇인가?
재귀란 함수가 자기 자신을 다시 호출하는 구조
조금 더 풀어 말하면, 어떤 문제를 더 작은 동일한 문제로 쪼갤 수 있을 때
그 작은 문제를 해결하기 위해 같은 함수를 다시 호출하는 방식
이다.
서로를 호출하는 경우도 재귀다
재귀는 꼭 “자기 자신만 호출”해야 하는 건 아니다.
예를 들어:
readValue() → readObject()
readObject() → readValue()
이처럼 함수들이 서로를 호출하며
사이클을 이루는 구조도 재귀다.
이를 간접 재귀(Indirect Recursion)라고 한다.
Call Stack과 재귀
자바스크립트는 함수 호출을 관리하기 위해
Call Stack(콜 스택)을 사용한다.
Call Stack이란?
함수를 호출하면 → 스택 맨 위에 쌓인다
함수가 종료되면 → 위에서부터 제거된다
구조는 후입선출(LIFO)
재귀 함수의 동작 방식
재귀 함수는 같은 함수가
콜 스택 위에 여러 번 쌓이는 구조로 동작한다.
그래서 종료 조건이 없으면…
👉 콜 스택이 계속 쌓인다
👉 결국 Stack Overflow 발생
재귀의 핵심 구성 요소
재귀 함수에는 반드시 두 가지가 필요하다.
1️⃣ 종료 조건 (Base Case)
재귀를 멈추는 조건.
if (n === 1) return 1;
이게 없으면 무한 호출이 발생한다.
2️⃣ 변화하는 입력값
매 호출마다 문제가 작아져야 한다.
factorial(n - 1)
입력값이 점점 줄어들어
결국 종료 조건에 도달해야 한다.
👉 이 구조는 for문의 조건식과 굉장히 비슷하다.
🔁 반복문 vs 재귀 (팩토리얼 예시)
반복문으로 구현
function factorial(n) {
let result = 1;
for (let i = 1; i <= n; i++) {
result *= i;
}
return result;
}
재귀로 구현
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
핵심 차이:
반복문 → 상태를 직접 관리
재귀 → “문제 축소”에 집중
재귀의 잠재적 위험
1️⃣ 종료 조건이 없거나 잘못된 경우
2️⃣ 반환값이 없는 경우
3️⃣ 입력값이 줄어들지 않는 경우
결과:
👉 스택 오버플로우
👉 재귀가 멈추지 않음
헬퍼 메소드 재귀
헬퍼 메소드 패턴은
외부 함수 안에 재귀 함수를 두는 방식이다.
이 방식은 상태 관리를 조금 더 직관적으로 할 수 있다.
function collectOddValues(arr) {
let result = [];
function helper(input) {
if (input.length === 0) return;
if (input[0] % 2 !== 0) {
result.push(input[0]);
}
helper(input.slice(1));}
helper(arr);
return result;
}
순수 재귀 (Pure Recursion)
순수 재귀는 외부 변수 없이
재귀 호출의 반환값만으로 문제를 해결하는 방식이다.
배열 복사 메소드들을 자주 사용한다.
slice, 전개 연산자 ..., concat
객체의 경우 Object.assign, ...
예제 문제
Q. 숫자 배열을 받아 모든 숫자의 곱을 반환하는
productOfArray 함수를 작성하시오.
function productOfArray(arr) {
// 종료 조건
if (arr.length === 0) return 1;
return arr[0] * productOfArray(arr.slice(1));
}실행 흐름 한 번에 이해하기
productOfArray([1,2,3])
→ 1 * productOfArray([2,3])
→ 2 * productOfArray([3])
→ 3 * productOfArray([])
→ 1스택에서 되돌아오면서 계산된다:
3 * 1
2 * 3
1 * 6
= 6