🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
재귀(recursion)
📍 재귀(recursion)
👉🏻 어떠한 것을 정의할 때 자기 자신을 참조하는 것
👉🏻 주로 함수를 정의할 때 사용하며, 재귀적으로 정의된 함수를 "재귀 함수"라고 함
[ recursion.mjs ]
//function myFunction(number) {
// console.log(number);
// myFunction(number + 1);
// }
// myFunction(1);
// 기저 조건(탈출 조건)이 없으므로 프로그램 자동 종료 = 언제 끝날지 예측 안 됨
// 숫자가 1~11111까지 출력됨(컴퓨터마다 메모리 공간이 달라 다르게 출력될 수 있음)
// 메모리 공간이 가득 차면 콜스택으로 자동 중단됨
function myFunction(number) {
if(number > 10) return; // 기저 조건 기술
console.log(number);
myFunction(number + 1);
}
myFunction(1);
📍 콜 스택(Call Stack)
👉🏻 함수가 호출되면서 올라가는 메모리 영역(=스택)
👉🏻 코드 - 데이터 - 힙 - 스택
👉🏻 FIFO 형식
👉🏻 함수를 호출하면 해당 함수가 콜 스택에 올라타고, 함수가 종료되면 해당 함수는 콜 스택에서 내려옴
👉🏻 A함수, B함수를 각각 호출할 때
funA();
funB();
A함수를 콜 스택에 올림 - A함수 종료 시 콜 스택에서 내린 후 B함수를 콜 스택 올림 - B함수 실행 - B함수 콜 스택에서 내림
👉🏻 A함수 안에서 B함수 호출할 때
funA();
function funA() { // 1) A함수 콜 스택에 올림
let A = 10;
let B = 5;
let C = funB(); // 2) A함수가 콜 스택에 올라간 상태에서 B함수 콜 스택에 올림
return a+ b+ c;
} // 4) A 함수 종료 시 콜 스택에서 내림
function funb() {
let a = 10;
let b = 5;
return a - b;
} // 3) B 함수 종료 시 콜 스택에서 내림
👉🏻 재귀 함수 호출 시
function myFunction(number) {
if(number > 3) return;
console.log(number);
myFunction(number + 1);
}
myFunction(1);
myFunction(1) 콜 스택 올림 - myFunction(2) 콜 스택 올림 - myFunction(3) 콜 스택 올림 - myFunction(4) 콜 스택 올린 후 if문에서 return 되어 종료되므로 myFunction(4) 콜 스택 제거 - myFunction(3) 더 이상 코드 없으므로 종료 - myFunction(2) 더 이상 코드 없으므로 종료 - myFunction(1) 더 이상 코드 없으므로 종료
👉🏻 호출할 때마다 스택 공간 차지
👉🏻 기저 조건이 없는 재귀 함수 호출 시 콜 스택에 함수가 끝도 없이 쌓이기 때문에 메모리가 부족해져 exception이 뜨는 것!
👉🏻 재귀 함수는 해결하기 힘든 상황(ex: 팩토리얼)을 해결하기 위해 자주 쓰임
📍 팩토리얼(Factorial)
[ factorial.mjs ]
function factorial(number) {
// 5! = 5 * 4 * 3 * 2 * 1
// 5! = 5 * 4!
// 5! = 5 * factorial(4)
// 4! = 4 * factorial(3)
if(number == 1 || number == 0) {
return 1;
} else {
return number * factorial(number - 1);
}
}
console.log(factorial(5)); // 120