재귀(Recursion)

• 재귀가 무엇인지를 알고, 어떻게 사용하는 지 공부하기
• 재귀 함수의 두가지 핵심 요소를 이해한다
• 호출 스택(call stack)을 시각화하여 디버깅하고 이해합니다
• helper method를 사용해서 재귀함수를 구성해봅니다.

재귀함수를 사용하는 이유

재귀란 무엇인가요?
재귀는 자기 자신을 호출하는 절차입니다. 여기서 말하는 재귀 함수는 자기 자신을 호출하는 함수가 되겠습니다.

왜 재귀를 알아야 할까요?
모든 곳에 사용되고 항상 사용됩니다. 예를들면 JSON.parse 에서도 재귀로 동작할 수 있습니다. 즉 여러곳에 응용될 수 있는 방법이기 때문에 이해해야합니다.

재귀를 사용함으로서 더욱 깔끔한 코드로 작성할 수 있습니다.

스택호출하기

거의 모든 프로그래밍 언어에는 보이지 않는 곳에서 함수 호출을 관리하는 일종의 데이터 구조가 있습니다.

자바스크립트의 경우 : 호출 스택 입니다. (스택이라는 데이터 구조)

자바스크립트가 반환 키워드(return)를 확인하거나, 함수 안에 더이상 실행할 코드가 없으면 컴파일러가 스택의 제일 위에 있는 항목을 제거합니다. (스택 구조)

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()

위의 코드를 보면서 생각해보겠습니다.
근복적인 개념은 함수를 호출하면 해당 함수가 스택의 맨 꼭대기에 추가되고 마찬가지로 꼭대기에서 한 번에 하나씩 제거된다는 것 입니다 (stack 데이터 구조 참고)

재귀함수의 경우 같은 함수가 스택에 여러개 쌓여있겠죠?

첫번째 재귀 함수

두가지 필수요소
1. 라인을 끝내는 종료 조건 (기반조건, base case)
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!")
}

위는 두가지 방법으로 만든 카운트 다운 함수 입니다.
재귀함수를 보시면 계속 호출되지만 입력되는 값음 3,2,1 로 다른 것을 확인할 수 있고 return으로 종료시점을 선언해 놓은 것을 볼 수 있습니다.

두번째 재귀 함수

function sumRange(num){
   if(num === 1) return 1; 
   return num + sumRange(num-1);
}

sumRange(4)

여기서는 return 이두개네요. 하나씩 생각해보면
1. 4가 입력됩니다
2. return 4 + sumRange(3) 이 실행되겠죠
3. sumRange(3)은 3+sumRange(2)를 반환하고
4. sumRange(2)은 2+sumRange(1)를 반환하고
5. sumRange(1)은 1을 반환 합니다.

다시 역으로 하나씩 수정해주면
4 + 3 + 2 + 1 이 되는 것을 이해할 수 있습니다.

반복문으로 팩토리얼 구현하기

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

재귀 호출로 팩토리얼 구현하기

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

통상적인 재귀의 잠재적 위험

1. 종료조건이 없는 경우(기반조건,base case) -> 무한 반복
2. 종료 조건은 있으나.... 입력값이 항상 같을 때 -> 무한 반복

위의 두가지 case에서는 무한반복이 발생하고 결국 모든 서비스를 멈추게 할 것이니 주의가 필요합니다.

helper 메소드 재귀

헬퍼 메소드 재귀는 "재귀형이 아닌 외부 함수"가 "재귀형인 내부 함수"를 호출하는 형태이다.

function collectOddValues(arr){
    
    let result = [];

    function helper(helperInput){
        if(helperInput.length === 0) {
            return;
        } // 종료조건, 길이가 0일때 
        
        if(helperInput[0] % 2 !== 0){
            result.push(helperInput[0])
        } // 홀수라면 추가
        
        helper(helperInput.slice(1))
    } // 재귀, 첫번째값 배고 입력
    
    helper(arr)

    return result;
}

collectOddValues([1,2,3,4,5,6,7,8,9])

위의 예시는 배열 중에서 홀수 숫자만 남기는 함수 입니다.

원함수 안에서 도와주는 역할을 하기 때문에 이러한 이름이 붙여진 것 같습니다.

순수 재귀

function collectOddValues(arr){
    let newArr = [];
    
    if(arr.length === 0) {
        return newArr;
    }
        
    if(arr[0] % 2 !== 0){
        newArr.push(arr[0]);
    }
        
    newArr = newArr.concat(collectOddValues(arr.slice(1)));
    return newArr;
}

collectOddValues([1,2,3,4,5])                 
     

같은 문제를 순수 재귀로 풀어본 코드 입니다. 한 문제를 푸는 방법은 여러가지가 있다는 것을 알 수 있죠.

자세히보면 방식이 조금 다릅니다. concat을 활용해서 배열에 하나씩 추가되는 방식을 사용했습니다. helper의 경우 잘라서 버리는 방식이였는데 조금 다른 것을 확인할 수 있네요.

tips :
1. 배열을 사용하고 헬퍼 메소드 없이 순수 재귀로 작성할 때 : slice, spread, concat 같은 메소드를 사용하자
2. 문자열은 변경이 불가능하기 때문에 slice나 substring을 활용해 사본을 만들어야 한다.
3. 객체의 경우 Object.assign이나 spread연산자를 사용하는 게 유용하다.