재귀 (Recursion)

재귀의 기본 개념

재귀는 문제를 더 작은 부분으로 나누어, 종료점에 도달할 때까지 반복적으로 수행하는 방법입니다.

 

목표

• 재귀가 무엇인지, 어떻게 유용하게 사용할 수 있는지 이해하기
• 재귀 함수 작성의 두 가지 핵심 요소
• 호출 스택이 재귀와 어떤 관련이 있는지 이해하기
• 헬퍼 메소드 재귀와 순수 재귀의 차이점과 비교

 

재귀 함수를 사용하는 이유

재귀는 자기 자신을 호출하는 절차로, 많은 상황에서 유용하게 사용됩니다. 복잡한 데이터 구조나 알고리즘을 다룰 때 재귀가 큰 도움이 될 수 있습니다.

예를 들어:

• JSON.parse / JSON.stringify
• document.getElementById와 같은 DOM 탐색 알고리즘
• 객체 순회 (Object traversal)
• 복잡한 알고리즘에서 재귀로 작성하는 것이 더 깔끔하고 이해하기 쉬운 경우가 많습니다.

 

호출 스택과 재귀

거의 모든 프로그래밍 언어에는 함수 호출을 관리하는 보이지 않는 데이터 구조가 있습니다. 호출된 함수는 다른 함수가 반환될 때까지 기다리며, 이를 관리하는 것이 호출 스택입니다. JavaScript의 경우 호출 스택이 이 역할을 담당합니다.

 

첫 번째 재귀 함수

어떤 재귀 함수든 반드시 갖춰야 하는 두 가지 요소가 있습니다.

1. 종료 조건 (Base Case)
2. 서로 다른 입력값 (Different Input)

// 카운트다운을 재귀로 구현하는 경우
function countDown(num) {
// 종료 조건
    if(num <= 0) {
        console.log("All done!");
        return;
    }
    console.log(num);
    // 서로 다른 입력값을 위한 --
    num--;
    countDown(num);
}

 

두 번째 재귀 함수

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

sumRange(3)을 호출했을 때,

3 + sumRange(2)
2 + sumRange(1)
1

이 순서대로 실행되어 6이 반환됩니다.

 

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

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);
}

 

재귀의 잠재적 위험

재귀 함수에는 몇 가지 잠재적 위험이 있습니다.

• 종료 조건이 없거나 잘못 설정된 경우
• 반환 값을 잊거나 잘못 반환하는 경우
• Maximum call stack size exceeded 에러 발생 (스택 오버플로우)

 

헬퍼 메소드 재귀

재귀 함수를 다른 함수로 감싸서 처리하는 방법입니다.

function collectOddValues(arr){
// 외부에 변수를 선언해서 활용
    let result = []
    function helper(helperInput){
        if(helperInput.length === 0) {
            return;
        }
        if(helperInput[0] % 2 !== 0){
            result.push(helperInput[0])
        }
        helper(helperInput.slice(1))
    }
    helper(arr)
    return result;
}

 

순수 재귀

외부 데이터 구조를 사용하지 않고 필요한 모든 코드가 함수 자체에 포함됩니다.

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;
}

 

• 배열을 사용하고 헬퍼 메소드 없이 순수 재귀 솔루션을 작성할 때 배열을 복사하는 slice, spread 연산자, concat 등을 사용할 수 있습니다.
• 문자열은 변경할 수 없으므로 slice, substr, 또는 substring을 사용해서 복사해야 합니다.
• 객체의 경우 Object.assign이나 spread 연산자를 사용할 수 있습니다.