Recursion (재귀함수)와 콜스택

🥓 재귀함수

• 자기 자신을 호출하는 절차이다.
• 한 가지 문제를 가지고 어떤 종료점(end point)에 도달할 때까지 더 작은 부분이나 변경되는 부분에서 반복적으로 수행하는 것
• 그 종료점을 종료 조건이라고 부른다.
• 보이지 않는 곳에서 작동하는 정적 데이터 구조

😊 call stack

: 대부분의 프로그래밍 언어에는 보이지 않는 곳에서 함수 호출을 관리하는 일종의 데이터 구조가 있다.
호출된 함수는 다른 함수가 return 될 때까지 기다리면서 특별한 순서가 생기게 된다.
제일 먼저 호출한 함수가 있다면 그 함수 안에서 두 번째 함수를 호출하는 것과 같은 순서말이다.
이렇게 순서대로 호출하는 데이터 구조가 자바스크립트에서는 호출 스택이다.

이 call stack는 종이 더미와 비슷하다고 생각하면 쉽다.
함수를 호출하면 call stack의 꼭대기에 쌓인다. 즉 종이 더미처럼 새로 추가하는 함수가 제일 꼭대기에 위치하게 된다.
만약 자바스크립트가 return keyword를 확인하거나 함수 안에 더이상 실행할 코드가 없다면 컴파일러가 스택에 제일 위에 있는 항목 을 지워버린다. 이렇게 더미에 비유하는 이유는 꼭 무엇인가를 꼭대기에 배치하기 때문이다.
무언가를 꺼낼때도 맨 위에서부터 꺼낸다.

함수가 실행되면 스택의 꼭대기에 추가되고 마찬가지로 꼭대기에서 한번에 하나씩 제거된다는 의미이다.

function takeShower(){
    return "Showering!"
}

function eatBreakfast(){
    let meal = cookFood()
    return `Eating ${meal}`
}

function cookFood(){
    let items = ["Oatmeal", "Eggs", "Protein Shake"]
    return items[Math.floor(Math.random()*items.length)];
}
function wakeUp() {
    takeShower()
    eatBreakfast()
    console.log("Ok ready to go to work!")
}

wakeUp()

이런 함수가 있을때 콜스택에 어떻게 쌓이는 지 살펴보자 call stack

먼저 wakeUp()이 실행되어 콜스택에 올라간다. wakeUp()

wakeUp()함수는 먼저 takeShower()함수를 실행한다. takeShower()
wakeUp()

takeShower()는 바로 "Showering"을 리턴하고 삭제된다. wakeUp()

wakeUp()에서 이제 eatBreakfast()를 실행한다. eatBreakfast()
wakeUp()

eatBreakfast()에서 다시 cookFood()를 호출한다. cookFood()
eatBreakfast()
wakeUp()

items에서 랜덤으로 값을 리턴하고 삭제된다. eatBreakfast()
wakeUp()

Eating {랜던 items}를 리턴하고 삭제된다. wakeUp()

ok ready to go to work를 찍고 종료된다. 제거

😘 재귀함수의 2가지 기본 요소

1. 라인을 끝내는 종료 조건
2. 다른 입력값

// Recursive Version
function countDown(num){
    if(num <= 0) {
        console.log("All done!");
        return;
    }
    console.log(num);
    num--;
    countDown(num);
}
countDown(3)

// Iterative Version
function countDown(num){
    for(var i = num; i > 0; i--){
        console.log(i);
    }
    console.log("All done!")
}

1. 숫자가 0보다 작아지면 종료되는 종료조건

2. num-- 로 달라지는 입력값