[자료 구조와 알고리즘] 재귀(recursion)

 

 

 

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘

 

재귀(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