재귀

재귀

스스로를 호출하는 함수

스택 호출하기

호출 스택은 자바스크립트의 보이지 않는 곳에서 작동하는 정적 데이터 구조이다. 함수를 호출하면 호출 스택(Call Stack)의 꼭대기에 쌓인다. 자바스크립트가 return keyword를 확인하거나 함수 내에 더이상 실행할 코드가 없으면 컴파일러가 스택의 제일 상단에 있는 항목부터 제거한다.
재귀 함수는 계속해서 새로운 함수(새로운 함수지만 동일 함수)를 호출 스택에 쌓고 쌓여진 함수는 호출을 대기한다.

재귀 함수의 동작

재귀 함수에는 두가지 요소가 필수적으로 필요하다.
1. 종료 조건(Base Case)
영원히 호출하지 않도록 종료 조건(재귀가 멈추는 시점)이 필요하다.
2. 매번 다른 입력값(감소하는 값)
재귀를 통해 계속 같은 함수를 호출하지만 매번 다른 데이터를 가지고 함수 호출한다. 입력값은 계속해서 감소하는 값으로 감소하다가 언젠가는 종료 조건을 만나고 재귀가 멈춘다.

countDown 예제

function countDown(num) {
    if (num <= 0) { // 종료 조건
        console.log('done!');
        return;
    }
    console.log(num);
    num--;
    countDown(num);
}
// countDown(3)
// print 3
// countDown(2)
// print 2
// countDown(1)
// print 1
// countDown(0)
// print "done!" 종료 조건

sumRange 예제

function sumRange(num) {
    if (num === 1) return 1; // 종료 조건
    return num + sumRange(num - 1);
}
// sumRange(3) => 3 + 2 + 1 = 6
// return 3 + sumRange(2) => 3 + 2 + 1
// return 2 + sumRange(1) => 2 + 1
// return 1 종료 조건 => 1

팩토리얼 예제

• 일반적인 for loop로 구현했을 때

function factorial(num) {
    let total = 1;
    for (let i = num; i > 0; i--) {
        total *= i
    }
    return total;
}

• 재귀로 구현했을 때

function factorial(num) {
    if (num === 1) return 1;
    return num * factorial(num - 1);
}

재귀에서 주의할 점

아래의 경우에 스택 호출 사이즈 초과(stack overflow) 에러가 나니 주의하자.

• 종료 조건이 없으면 코드가 계속 실행되면서 스택에 계속 함수 추가
• 잘못된 값을 반환하거나, 반환을 안하면 스택에 계속 함수 추가

---

✍️ <JavaScript 알고리즘 & 자료구조 마스터클래스> 강의를 들으며 알게 된 내용을 정리하였습니다.