[JS] 재귀 기능

🚀 재귀(Recursion)란?

재귀는 함수가 자기 자신을 호출하는 방식
즉, 어떤 문제를 같은 구조의 더 작은 문제로 나누어 해결하는 방식이다.

 

📌 재귀의 기본 구조

function recursiveFunction() {
  // 1️⃣ 종료 조건 (Base Case)
  if (조건) {
    return;  // 재귀를 멈추는 조건
  }

  // 2️⃣ 재귀 호출 (Recursive Case)
  recursiveFunction();  // 자기 자신을 호출
}

✅ 중요한 개념:

• 반드시 종료 조건(Base Case)이 있어야 한다!
  • 종료 조건이 없으면 함수가 무한히 실행되어 **스택 오버플로우(Stack Overflow)**가 발생한다

---

🔥 예제 1: 1부터 n까지 출력하는 재귀 함수

function printNumbers(n) {
  if (n === 0) return;  // 종료 조건 (n이 0이면 종료)
  
  printNumbers(n - 1);  // n-1을 재귀 호출
  console.log(n);       // 호출이 끝난 후 출력
}

printNumbers(5);

 

📌 실행 과정

함수 호출	동작	출력
printNumbers(5)	printNumbers(4) 호출
printNumbers(4)	printNumbers(3) 호출
printNumbers(3)	printNumbers(2) 호출
printNumbers(2)	printNumbers(1) 호출
printNumbers(1)	printNumbers(0) 호출
printNumbers(0)	종료
함수가 돌아오면서	console.log(1)	1
	console.log(2)	2
	console.log(3)	3
	console.log(4)	4
	console.log(5)	5

 

✅ 출력 결과:

1
2
3
4
5

 

• printNumbers(5)는 printNumbers(4)를 호출하고, printNumbers(4)는 printNumbers(3)을 호출하는 재귀 호출을 함.
• 재귀 함수가 끝날 때(n === 0)부터 하나씩 돌아오면서 출력이 됨.

~-> 역시나 이해가 어렵다면 실행과정을 좀 더 찬찬히 들여다보자!

✅ 실행 과정 살펴보기

이 코드는 printNumber(5)를 호출하면서 printNumber(4), printNumber(3)... 이렇게 계속 호출한다.

1️⃣ printNumber(5)를 호출하면
→ printNumber(4) 호출
2️⃣ printNumber(4)는
→ printNumber(3) 호출
3️⃣ printNumber(3)는
→ printNumber(2) 호출
4️⃣ printNumber(2)는
→ printNumber(1) 호출
5️⃣ printNumber(1)는
→ printNumber(0) 호출
6️⃣ printNumber(0)은 종료 조건을 만나 리턴됨(끝남).

이제 호출한 순서의 반대로 함수가 돌아오면서 console.log(n)이 실행됨!

 

📌 스택(Stack) 개념을 적용해 보자!

자바스크립트에서 함수가 실행될 때, 스택(stack) 이라는 구조를 사용해.
재귀 함수가 호출될 때마다 스택에 쌓이고, 종료 조건을 만나면 쌓인 순서대로 다시 돌아와 실행돼.

printNumber(5) 호출 → printNumber(4) 호출 → printNumber(3) 호출 → printNumber(2) 호출 → printNumber(1) 호출 → printNumber(0) 호출 → 종료!

 

이제 쌓인 순서의 반대로 하나씩 실행됨!

printNumber(1) 실행 → printNumber(2) 실행 → printNumber(3) 실행 → printNumber(4) 실행 → printNumber(5) 실행

즉, console.log(n); 이 재귀가 끝난 후 차례대로 실행되면서 1부터 5까지 출력된다.

 

📌 실행 흐름을 표로 정리하면

호출된 함수	스택에 쌓이는 과정	스택에서 빠지는 과정 (console.log 실행)
printNumber(5)	printNumber(5) 호출	console.log(5) 실행
printNumber(4)	printNumber(4) 호출	console.log(4) 실행
printNumber(3)	printNumber(3) 호출	console.log(3) 실행
printNumber(2)	printNumber(2) 호출	console.log(2) 실행
printNumber(1)	printNumber(1) 호출	console.log(1) 실행
printNumber(0)	return (종료)	-

 

📌 실제 코드 실행 결과

printNumber(5);

 

🔽 출력

1
2
3
4
5

왜 5부터 안 나오고 1부터 나올까? 🤔
→ console.log(n)이 재귀 호출 후 실행되기 때문!
즉, printNumber(5)가 printNumber(4)를 호출하고, 모든 재귀가 끝난 뒤 console.log(n)이 실행됨.

 

📌 한 줄 요약

 

• 재귀 함수는 먼저 호출이 계속 쌓였다가(push), 종료 조건을 만나면서 하나씩 빠지면서(pop) 실행된다.
• 그래서 작은 숫자부터 출력되는 것!
• 이걸 스택(Last In, First Out) 구조라고 한다.

 

---

🔥 예제 2: 팩토리얼 (Factorial) 계산

팩토리얼(n!)은 n * (n-1) * (n-2) * ... * 1을 계산하는 함수야.

 

function factorial(n) {
  if (n === 1) return 1;  // 종료 조건
  return n * factorial(n - 1);  // 재귀 호출
}

console.log(factorial(5));  // 5! = 5 × 4 × 3 × 2 × 1 = 120​

 

✅ 출력 결과:

120

📌 실행 과정

함수 호출	동작
factorial(5)	5 * factorial(4)
factorial(4)	4 * factorial(3)
factorial(3)	3 * factorial(2)
factorial(2)	2 * factorial(1)
factorial(1)	1 반환
돌아오면서	2 * 1 = 2
	3 * 2 = 6
	4 * 6 = 24
	5 * 24 = 120

팩토리얼 계산도 재귀로 하면 아주 쉽게 구현할 수 있다! 💡

---

🛑 재귀를 사용할 때 주의할 점

• 종료 조건(Base Case)을 반드시 확인!
  • 종료 조건이 없으면 무한 루프에 빠져서 프로그램이 멈추지 않음.
• 스택 오버플로우(Stack Overflow) 주의!
  • 너무 깊은 재귀 호출이 발생하면 메모리 초과가 될 수 있다.
  • 이런 경우 반복문(while, for)으로 변환하는 게 더 나을 수도 있다.

 

---

🚀 재귀 vs 반복문

✅ 재귀

✔ 코드가 직관적이고 짧아짐.
✔ 트리, 그래프 탐색 등에서 유용함.
❌ 스택 메모리를 많이 사용해 비효율적일 수도 있음.
❌ 깊이(depth)가 커지면 스택 오버플로우 발생 가능.

✅ 반복문

✔ 메모리를 절약할 수 있음.
✔ 성능이 재귀보다 더 좋을 때가 많음.
❌ 코드가 길어질 수 있음.

---

✅ 결론

• DFS, 팩토리얼, 피보나치 수열 같은 경우는 재귀가 유용함.
• 하지만 재귀 호출이 너무 많아지면 반복문으로 해결하는 것이 좋음.

 

*위 포스팅은 챗GPT 답변을 토대로 작성했습니다!