05 재귀

5.1 재귀함수를 사용하는 이유

  우선 재귀라는것이 무엇일까? 모던 자바스크립트에서도 공부했듯이 재귀는 자기 자신을 호출하는 함수를 의미한다. 그렇다면 재귀를 왜 알아야 할까? 코드를 작성하는데 모든 곳에서 활용될 수 있기 때문이다. 우선 재귀를 이해하기 위해서는 '실행컨텍스트 스택'을 이해할 필요가 있다. 실행 컨텍스트는 이미 모던 자바스크립트에서 공부한적이 있다. 

2022.07.20 - [언어 공부 및 정리/자바스크립트[모던자바스크립트]] - 23장 실행 컨텍스트

23장 실행 컨텍스트

  간단히 다시 생각해 보자면 실행 컨텍스트 스택은 자바스크립트 엔진이 코드를 실행함에 있어 일의 처리 순서를 관리하는 툴이라고 생각하면 될 것 같다.

 

  우선 재귀는 두 가지 조건을 꼭 지켜서 작성해야 한다. 첫 번째 조건은 반드시 종료 조건이 있어야 한다. 그렇지 않으면 무한루프에 빠지기 때문이다. 두 번째 조건은 재귀 함수 호출시 매개변수의 변화가 있어야 한다. 그렇지 않으면 똑같은 함수가 무한 반복되어 무한 루프에 빠지기 때문이다. 그렇다면 이제 카운트 다운을 할 수 있는 함수를 만들어 보자! 

// 반복문으로 작성한 카운트 다운
function countDown(num){
    for(var i = num; i > 0; i--){
        console.log(i);
    }
}



// 재귀함수로 작성한 카운트 다운
function countDown(num){
    if(num <= 0) {
        return;
    }
    console.log(num);
    num--;
    countDown(num);
}
countDown(3)

  이번에는 재귀함수를 설명할때 가장 많이 등장하는 팩토리얼을 작성해 보자. 팩토리얼은 1부터 주어진 정수까지 모두 곱하는것을 말한다.

 //for 반복문으로 팩토리얼 구하기
function factorialll(num){
    let facNum = 1;
    for(let i = num ; i > 0 ; i--){
        facNum *= i;
    }
    return facNum;
}

console.log(factorialll(5));


//while 반복문으로 팩토리얼 구하기
function fff(num){
    if(num <= 0) return 1

    let res = num;
    while(--num) res *= num;
    return res;
}

console.log(fff(5));


//재귀함수로 팩토리얼 구하기
function factorial(n){
    if(n <= 0)return 1;
    return n * factorial(n-1);
}

console.log(factorial(3));

  위와 같이 재귀함수는 반복문을 통해서 구현할 수도 있지만, 재귀함수를 사용함으로서 매우 간결하게 코드를 작성할 수 있다. 

 

  재귀 함수를 작성할때 주의해야 할 점을 살펴보자면 재귀함수에서 종료 조건이 없거나 잘못되는 경우는 앞에서 설명했듯이 무한루프에 빠져 스택오버플로우가 발생할 수 있다. 그렇기 때문에 종료조건을 반드시 만들어줘야 하고, 반환을 잊거나 잘못된 반환을 해도 스택오버플로우가 발생할 수 있으니, 꼭 종료 조건을 만들어 줘야 한다!!

 

5.2 헬퍼 메서드 재귀

  헬퍼 메서드 재귀는 외부 함수의 중첩 함수가 재귀함수인 경우, 헬퍼 메서드 재귀라고 부른다. 쉽게 말해, 내부함수 즉, 중첩함수를 재귀함수로 만드는 것이다. 예를 들어 어느 배열에서 모든 홀수값을 수집하는 것과 같은 작업을 수행하고 있다면 헬퍼 메서드 재귀를 사용하는게 아주 좋은 전략이자 접근법이다. 헬퍼 메서드 재귀는 일종의 결과를 컴파일할 때 흔히 사용되는 패턴이다. 보통 배열에서 많이 사용된다. 하지만, 반복문보다 재귀를 사용해서 해결하는것이 조금 더 복잡한 방법일 수 있다.

function oddValues(array){

    let result = []

    function helper(input){
        if(input.length === 0) {
            return;
        }

        if(input[0] % 2 !== 0){
            result.push(input[0])
        }

        helper(input.slice(1))
    }

    helper(array)

    return result;

}
console.log(oddValues([1,2,3,4,5,6])); // [1,3,5]

5.3 순수 재귀

  위의 코드를 순수 재귀를 통해서 작성할 수도 있다. 주의해야 할 점은 result배열은 함수가 호출 될 때마다 빈 배열을 생성한다는 것을 주의해야 한다.

function oddValues(array){
    let result = [];

    if(array.length === 0) {
        return result;
    }

    if(array[0] % 2 !== 0){
        result.push(array[0]);
    }

    result = result.concat(oddValues(array.slice(1)));
    return result;
}

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

//slice(1)  << 배열의 1번 인덱스를 제외하고 나머지 인덱스를 복사해서 반환
//concat() << 인수로 전달된 값들을 원본 배열의 마지막 요소로 추가한 새로운 배열을 반환
//즉, result[1] -> result[3] -> result[5] -> 반환값[5] -> 반환값[3,5] -> 반환값[1,3,5]