🌀 재귀함수(Recursion) 이해하기

재귀함수는 자기 자신을 호출하는 함수입니다.
복잡한 반복문 대신 문제를 더 작은 단위로 쪼개서 해결할 수 있게 도와주는 핵심 개념입니다.

1️⃣ 재귀함수의 핵심 개념

재귀(recursion)는 어떤 문제를

"같은 구조의 더 작은 문제로 나누어 푸는 방식"
으로 접근합니다.

• 문제를 나누고 (Divide)
• 더 이상 나눌 수 없는 기저 조건(Base Case) 에서 멈추며
• 나눈 결과를 조합(Combine)합니다.

2️⃣ 재귀함수의 구조

재귀함수는 보통 다음 두 부분으로 구성됩니다 👇

🧐 예시: 1부터 n까지의 합

function sum(n: number): number {
  if (n === 1) return 1;       // ✅ 기저 조건
  return n + sum(n - 1);       // 🔁 재귀 호출
}

console.log(sum(5)); // 15

3️⃣ 재귀 호출 흐름 시각화

sum(3) 호출 시의 실행 흐름은 다음과 같습니다.

sum(3)
→ 3 + sum(2)
→ 3 + (2 + sum(1))
→ 3 + (2 + 1)
= 6

4️⃣ 재귀함수의 장단점

5️⃣ 재귀 vs 반복 비교

6️⃣ 예시: 피보나치 수열

function fib(n: number): number {
  if (n <= 1) return n;             // ✅ 기저 조건
  return fib(n - 1) + fib(n - 2);   // 🔁 재귀 호출
}

console.log(fib(6)); // 8

📈 호출 흐름 (fib(4))

fib(4)
→ fib(3) + fib(2)
→ (fib(2) + fib(1)) + (fib(1) + fib(0))
→ ((fib(1) + fib(0)) + 1) + (1 + 0)
→ ((1 + 0) + 1) + (1 + 0)
= 3

// 중복된 함수를 호출하여 메모이제이션으로 최적화 가능 (fib(1) 여러번 호출)

하지만 이 방식은 중복 호출이 많아서 비효율적입니다.
이럴 땐 메모이제이션(Memoization) 혹은 반복문으로 변환하는 것이 좋습니다.

7️⃣ 재귀함수와 스택 프레임

재귀 함수가 호출될 때마다 스택 프레임(Stack Frame) 이 생성됩니다.
스택 프레임은 함수의 실행 정보를 저장하는 공간으로, 함수가 끝나면 사라집니다.

🔹 스택 프레임 구성 요소

1. 매개변수(Parameter)

• 함수가 호출될 때 전달되는 입력 값

2. 지역 변수(Local Variable)

• 함수 내부에서 선언된 변수

3. 리턴 주소(Return Address)

• 함수 실행 종류 후 어디로 돌아갈지 저장

⚠️ 재귀 호출이 깊어질수록 스택 프레임이 쌓이므로, 기저 조건이 없으면 Stack Overflow 에러가 발생할 수 있습니다.

🧐 예시 1: sum(3)

function sum(n: number): number {
  if (n === 1) return 1;       
  return n + sum(n - 1);       
}

sum(3);

🥞 호출 스택 상태

┌─────────────┐
│ sum(1)      │  ← n=1, return → sum(2)
└─────────────┘
┌─────────────┐
│ sum(2)      │  ← n=2, return → sum(3)
└─────────────┘
┌─────────────┐
│ sum(3)      │  ← n=3, return → main
└─────────────┘

• 각 사각형은 스택 프레임을 나타냄

• 각 스택 프레임 안에는 매개변수, 지역 변수, 리턴 주소 정보가 들어 있음

• 맨 위 프레임부터 실행 중

• 실행 종료 시 pop → 아래 프레임으로 반환

🧐 예시 2: 피보나치 수열 fib(4)

function fib(n: number): number {
  if (n <= 1) return n;             
  return fib(n - 1) + fib(n - 2);   
}

fib(4);

🥞 호출 스택 상태

┌─────────────┐
│ fib(1)      │ n=1, return → fib(2)
└─────────────┘
┌─────────────┐
│ fib(0)      │ n=0, return → fib(2)
└─────────────┘
┌─────────────┐
│ fib(2)      │ n=2, return → fib(3)
└─────────────┘
┌─────────────┐
│ fib(1)      │ n=1, return → fib(3)
└─────────────┘
┌─────────────┐
│ fib(3)      │ n=3, return → fib(4)
└─────────────┘
┌─────────────┐
│ fib(4)      │ n=4, return → main
└─────────────┘