재귀 (Recursion)
: 어떤 것을 정의할 때, 자기 자신을 참조하는 것
- 재귀함수: 자기 자신을 호출하는 함수
- 재귀함수는 메모리 공간을 많이 차지함
- 재귀함수의 필요성: 팩토리얼
function myFunction(number) {
consloe.log(number);
myFunction(number + 1);
}
myFunction(1); // 무한 호출 → 메모리 초과 발생하여 자동 종료
재귀함수의 필수 조건
- 기저 조건( = 탈출 조건, Base Case)이 반드시 있어야 함
- 기저 조건이 없으면 무한 루프가 발생하고 메모리 초과가 일어남
- 기저 조건이 없으면 무한 루프가 발생하고 메모리 초과가 일어남
function myFunction(number) {
if(number > 10) return;
consloe.log(number);
myFunction(number + 1);
}
myFunction(1); // 1부터 10까지 출력
재귀함수 쉽게 구현하기
1. 문제 분해 (하위 문제로 나누기)
- 큰 문제를 똑같은 형태의 더 작은 문제로 쪼갤 수 있는지 생각하기
- 5! → 5 * 4!
⇒ n! = n * (n - 1)!
2. 재귀 호출 가정 및 규칙 찾기
- 문제 전체의 답이 작은 문제들의 답으로 어떻게 표현되는지 관계를 찾기
- factorial(4)가 이미 제대로 작동한다고 생각하고, factorial(5)는 5 * factorial(4)라고 구현한다.
3. 기저 조건(Base case)
- 더 이상 쪼갤 수 없거나, 답을 바로 알 수 있는 상황을 정의하기
- 종료 조건이 없으면 함수가 무한히 호출돼서 에러가 남
- 무한 호출을 막기 위해, factorial(1)이나 factorial(0)에서는 더 이상 재귀 호출하지 않고 바로 1을 리턴한다.
function factorial(number) {
if (number === 0 || number === 1) {
return 1; // ✅ 기저 조건
} else {
return number * factorial(number - 1); // ✅ 재귀 호출 (자기 자신을 믿고 사용)
}
}
콜스택 (Call Stack)
: 함수가 호출되면서 올라가는 메모리 영역
- 함수 실행 정보를 저장하는 메모리 공간
- 스택(Stack) 구조
- FILO(First In Last Out) 특성을 갖고 있음
- 함수를 호출하면 이 함수는 콜스택에 올라가게 되고, 함수가 종료되면 콜스택에서 제거됨
콜스택 예시: 함수 A에서 함수 B 호출하는 재귀함수
함수 A
function funcA() {
let a = 10;
let b = 5;
let c = funcB(); // B 함수를 호출
return a + b + c;
}
함수 B
function funcB() {
let a = 10;
let b = 5;
return a - b;
}
실행 과정
- 함수 A를 호출하면 이 함수는 콜스택에 올라감
- A 함수를 실행하는 도중에 B 함수를 호출함
- A 함수는 종료되지 않았기 때문에 콜스택에서 제거되지 않음
- 콜스택에서 A 함수 위에 B 함수가 올라가게 됨
- A 함수 내부의 B 함수가 실행됨
- B 함수의 실행이 끝나면, 콜스택에서 B 함수가 제거됨
- A 함수는 나머지 코드를 실행시키고 함수를 종료, 콜스택에서 제거됨
콜스택 예시: 함수 속에서 함수를 호출하는 재귀함수
function myFunction(number) {
if(number > 3) return;
consloe.log(number);
myFunction(number + 1);
}
myFunction(1);
실행 과정
- myFunction(1) 호출
→ 콜스택: [myFunction(1)] - myFunction(1)이 실행되면서 조건 확인, 조건(number > 3)은 거짓 → myFunction(2) 호출
→ 콜스택: [myFunction(1), myFunction(2)] - myFunction(2)가 실행되면서 조건 확인, 조건(number > 3)은 거짓 → myFunction(3) 호출
→ 콜스택: [myFunction(1), myFunction(2), myFunction(3)] - myFunction(3)이 실행되면서 조건 확인, 조건(number > 3)은 거짓 → myFunction(4) 호출
→ 콜스택: [myFunction(1), myFunction(2), myFunction(3), myFunction(4)] - myFunction(4)이 실행되면서 기저 조건을 확인하고, if문이 참이기 때문에 return하고 종료됨
- myFunction(4) 종료 → 콜스택에서 제거
- 더 이상 실행할 코드가 없으므로 차례로 myFunction(3), myFunction(2), myFunction(1)이 종료되며 콜스택에서 제거됨
재귀함수 예시: 재귀함수로 팩토리얼 5! 구현하기
- 팩토리얼(Factorial): n이 주어질 때, 1부터 n까지 모든 수의 곱
n! = n × (n - 1) × (n - 2) × ... × 1
// ex) 5! = 5 * 4 * 3 * 2 * 1 = 120function factorial(number) {
if(number === 1 || number === 0) {
return 1;
} else {
return number * factorial(number - 1);
}
}
console.log(factorial(5)); // 120
실행 흐름 (5!)
- 5 * factorial(4)
→ 4 * factorial(3)
→ 3 * factorial(2)
→ 2 * factorial(1)
→ 1 → return 1
실제 계산 순서
- factorial(5) → 5 * 24 = 120
- factorial(4) → 4 * 6 = 24
- factorial(3) → 3 * 2 = 6
- factorial(2) → 2 * 1 = 2
- factorial(1) → return 1
재귀 패턴
1. 단순한 반복 실행
- 콜스택에 공간을 많이 차지해 for문보다 성능이 좋지 않음
function myFunction(number) {
if(number > 3) return;
consloe.log(number);
myFunction(number + 1);
}
myFunction(1); // 1, 2, 3 출력
2. 하위 문제의 결과를 기반으로 현재 문제를 계산함
return number * factorial(number - 1);
상향식 vs 하향식 계산
- 상향식 계산 방식은 for문이나 재귀함수로 구현할 수 있지만, 하향식 계산 방식은 재귀함수로만 구현할 수 있음
| 방식 | 설명 | 구현 |
| 상향식 | 작은 값부터 차례대로 쌓아올림 | for문, 재귀함수로도 구현 가능 |
| 하향식 | 큰 문제를 작게 나눠 해결 | 재귀함수로만 구현 가능 |
- 팩토리얼은 재귀 함수 뿐만 아니라 for문을 사용해서도 구현할 수 있음
⇒ 상향식 계산
function myFunction(number) {
let sum = 1;
for(let i = 1; i <= number; i++) {
sum *= 1;
}
return sum;
}
- 재귀함수를 이용한 계산 방식
⇒ 하향식 계산
function factorial(number) {
if(number === 1 || number === 0) {
return 1;
} else {
return number * factorial(number - 1);
}
}
console.log(factorial(5));
하향식 계산 예시: 배열의 모든 원소의 합([ 1, 2, 3, 4, 5 ])을 구하기
- 하위 문제: 1 ~ 4까지 더하는 문제
- 하위 문제에 5만 더하면 해결
function sumArray(arr) {
if(arr.lenght === 1) return arr[0];
return sumArray(arr.slice(0, -1)) + arr[arr.length - 1]; // 1 ~4까지의 합 + 5
}
let arr = [1, 2, 3, 4, 5];
let sum = sumArray(arr);
console.log(sum); // 15
하향식 계산 예시: 문자열의 길이를 계산하는 strLength() 함수 구현하기
- 하위문제: 구하려는 문자열의 마지막 원소를 제외한 나머지 부분
- 하위문제에 마지막 문자열 1을 더하면 해결
function strLength(arr){
if(arr[0] == null) return 0;
return strLength(arr.slice(0, -1)) + 1; // 뒤에서 2번째 문자열까지의 길이 + 마지막 문자열 1
}
let str = "abcde";
let len = strLength(str);
console.log(len); // 5
하향식 계산 예시: 지수 함수를 재귀함수를 이용해 하향식으로 구현하기
- 2⁵ = 2를 5번 곱하기(2는 x, 5는 n)
- 하위문제: 2의 4승(16)
- 하위문제에 2를 곱하면 해결
function power(x, n){
if(n == 0) return 1;
return power(x, n - 1) * x; // 2의 4승 * 2
}
console.log(power(2, 5)); // 32
하노이 탑
: 원반들을 한 기둥에서 다른 기둥으로 옮기는 퍼즐 게임
- 한 번에 하나의 원반만 옮길 수 있음
- 큰 원반은 작은 원반 위에 놓을 수 없음
하노이 탑을 하향식 접근으로 구현하기
function hanoi(count, from, to, temp){
if(count == 0) return; // 옮길 원반이 없으면 종료
hanoi(count - 1, from, temp, to);
// 원반 1, 2를 기둥 A에서 기둥 B로 이동, C는 이동을 위해 임시로 사용
// 원반 3을 기둥 A → C로 이동(그냥 콘솔에 기록)
console.log(`${count} ${from} -> ${to}`);
hanoi(count - 1, temp, to, from);
// 원반 1, 2를 기둥 B에서 기둥 C로 이동, A는 이동을 위해 임시로 사용
}
hanoi(3, "A", "C", "B");
// 원반이 3개, 기둥 A에서 시작(from), 기둥 B는 임시로 이용(temp), 기둥 C는 목표 기둥(to)
핵심 구조
hanoi(count - 1, from, temp, to); // 1단계
console.log(`${count} ${from} -> ${to}`); // 2단계
hanoi(count - 1, temp, to, from); // 3단계
- n번 원반을 A → C로 옮기기 위해
- n-1번 원반을 A → B (보조 기둥 C 사용)
- n번 원반을 A → C로 직접 이동
- n-1번 원반을 B → C (보조 기둥 A 사용)
실행 흐름
- hanoi(3, A, C, B)
├─ hanoi(2, A, B, C) ← 원반 1, 2를 A → B
│ ├─ hanoi(1, A, C, B) ← 원반 1을 A → C
│ │ ├─ hanoi(0) → 종료
│ │ └─ 🔹 이동: 1 A → C
│ │ └─ hanoi(0) → 종료
│ └─ 🔹 이동: 2 A → B
│ └─ hanoi(1, C, B, A) ← 원반 1을 C → B
│ ├─ hanoi(0) → 종료
│ └─ 🔹 이동: 1 C → B
│ └─ hanoi(0) → 종료
├─ 🔹 이동: 3 A → C ← 원반 3이 이때 A → C
└─ hanoi(2, B, C, A) ← 원반 1, 2를 B → C
├─ hanoi(1, B, A, C) ← 원반 1을 B → A
│ ├─ hanoi(0) → 종료
│ └─ 🔹 이동: 1 B → A
│ └─ hanoi(0) → 종료
└─ 🔹 이동: 2 B → C
└─ hanoi(1, A, C, B) ← 원반 1을 A → C
├─ hanoi(0) → 종료
└─ 🔹 이동: 1 A → C
└─ hanoi(0) → 종료
최종 출력 순서
- 1 A → C
- 2 A → B
- 1 C → B
- 3 A → C
- 1 B → A
- 2 B → C
- 1 A → C