🔄 1. 재귀의 핵심: 두 가지 사고방식

재귀는 문제를 **'반복'**으로 풀 것인가, 아니면 **'작은 문제의 조합'**으로 풀 것인가의 차이입니다.

① 반복적 사고 (Iterative)

for나 while 루프를 사용해 결과를 누적합니다. 메모리 사용량이 고정되어 있어 효율적입니다.

② 재귀적 사고 (Recursive)

목표 작업을 **'가장 단순한 동작(Base)'**과 **'자기 자신을 포함한 변형된 작업(Recursive step)'**으로 나눕니다.

• Base (기본): 재귀를 멈추는 지점. (예: $n = 1$)
• Recursive step (재귀 단계): 문제를 더 작게 쪼개어 자신을 호출하는 과정.

---

🧠 2. 실행 컨텍스트와 스택 (The Memory)

재귀가 어떻게 동작하는지 이해하려면 엔진 내부의 **실행 컨텍스트(Execution Context)**를 알아야 합니다.

1. 함수 호출: 새로운 실행 컨텍스트가 생성됩니다. (변수, 현재 실행 지점 등 저장)
2. 중첩 호출: 현재 컨텍스트를 실행 컨텍스트 스택에 잠시 보관(Push)하고, 새 호출을 실행합니다.
3. 종료 및 복구: 가장 마지막 호출이 끝나면 스택에서 이전 컨텍스트를 꺼내(Pop) 중단됐던 지점부터 다시 시작합니다.

⚠️ 주의: 재귀 깊이(Recursion Depth)

자바스크립트 엔진은 스택의 크기를 제한합니다. 대개 10,000개 정도가 한계이며, 이를 넘으면 Maximum call stack size exceeded 에러가 발생합니다.

---

🌳 3. 재귀적 순회 (Recursive Traversal)

재귀가 가장 빛나는 순간은 깊이를 알 수 없는 중첩 구조를 다룰 때입니다.

• 시나리오: 회사의 부서별 급여 합계를 구해야 하는데, 어떤 부서는 직원이 있고 어떤 부서는 하위 부서가 또 있는 경우.
• 해결: * 배열(직원 목록)을 만나면 합계를 구한다 (Base).
  • 객체(하위 부서)를 만나면 그 객체의 각 값에 대해 다시 함수를 호출한다 (Recursive step).

---

🔗 4. 재귀적 자료구조: 연결 리스트 (Linked List)

배열은 중간 요소를 삭제하거나 앞에 추가할 때 인덱스를 모두 밀어야 하므로 $O(n)$의 비용이 듭니다. 반면 연결 리스트는 각 요소가 다음 요소를 가리키는 구조여서 삽입/삭제가 매우 빠릅니다.

• 구조: list = { value, next }
• 특징: 재귀적으로 정의되어 있어, 재귀 함수와 궁합이 매우 좋습니다.

---

🎙️ 기술 면접 대비 (Interview Questions)

Q1. 재귀와 반복문의 성능 차이를 설명해 주세요. (중급)

답변: 반복문은 하나의 실행 컨텍스트 내에서 변수만 업데이트하므로 메모리 사용량이 적고 빠릅니다. 반면 재귀는 호출마다 새로운 컨텍스트를 스택에 쌓아야 하므로 메모리 비용이 더 크고 속도가 약간 느릴 수 있습니다. 하지만 코드가 훨씬 간결하고 복잡한 트리 구조를 순회할 때 가독성이 압도적으로 좋습니다.

Q2. 피보나치 수열을 재귀로 구현할 때 발생하는 문제와 해결책은? (심화)

답변: 단순 재귀로 구현하면 동일한 값을 구하는 중복 호출이 기하급수적으로 늘어나 성능이 저하됩니다($O(2^n)$). 이를 해결하기 위해 **메모이제이션(Memoization)**을 사용하여 이미 계산된 값을 저장하거나, 작은 값부터 계산해 올라가는 바텀업(Bottom-up) 방식의 반복문을 사용해야 합니다.

Q3. '꼬리 재귀 최적화(Tail Call Optimization)'란 무엇인가요? (심화)

답변: 함수의 마지막 동작이 재귀 호출인 경우, 엔진이 이전 컨텍스트를 유지할 필요가 없다고 판단하여 스택을 새로 쌓지 않고 재사용하는 최적화 기법입니다. 이를 지원하는 엔진에서는 재귀 깊이 제한 없이 안전하게 재귀를 쓸 수 있지만, 안타깝게도 모든 자바스크립트 엔진이 이를 완벽히 지원하지는 않습니다.

---