많은 곳에 쓰이는 재귀

재귀는 자기자신을 호출하는 절차입니다. 프로그래밍에서 재귀 함수라하면 자기 자신을 호출하는 함수를 뜻하게 됩니다.

Java Script 에서 재귀는 많은 곳에서 사용되고있습니다.

• JSON.parse / JSON.stringify
• document.getElementById과 같은 DOM 요소 순회
• 객체 순회

공부를 하기 전에는 생각 없이 사용했는데, 의외로 자주 사용하고 있었습니다. 그만큼 재귀는 중요한 개념이 아닐까 싶습니다.

Call Stack

많은 언어에는 함수 호출을 관리하는 일종의 데이터 구조가 있습니다.
함수가 순서대로 실행되도록 관리되는데 JavaScript에서 이것을 call stack이라고 부릅니다.
함수가 호출될 때 Call Stack에 하나씩 쌓이게 되고 함수가 'reutrn' 키워드를 만나거나 함수가 종료되었을 때 컴파일러는 해당 함수를 Call Stack에서 제거하게 됩니다.

일반적으로 함수의 경우에는 call stack에 추가되고 제거되는 과정을 반복하게 되는데 재귀의 경우에는 재귀 함수가 계속해서 call stack에 쌓이게 됩니다.

재귀 함수에서 중요한 개념

앞서 언급했듯이 재귀는 자기자신을 호출하는 절차입니다. 이 호출을 끝내기 위해서는 중단점(Break Point)가 있어야 합니다. 이 중단점을 종료 조건(Base Case)라고 부릅니다. 이 중단점 개념은 for문 같은 Loop 에서 중단점이 있어야하는 것처럼 중요합니다. 호출이 중단되지 않으면 컴퓨터가 계속해서 연산을 하기 때문에 굉장히 느려집니다.

그리고 두번째는 '달라지는 input 값'입니다. 재귀 함수에서 input은 계속 다른 값을 넣어야합니다. 그렇지 않으면 재귀를 사용하는 의미가 없겠죠.

예시

첫번째 예시

하나의 숫자를 매개변수로 받아 숫자를 1씩 감소하며 console에 출력하는 함수를 반복문과 재귀로 만들어 보겠습니다.

function countdownWithLoop(num){
    for(var i = num; i > 0; i--){
        console.log(i);
    }
    console.log("끝!")
}

countdownWithLoop(5);

반복문으로 만든 함수는 코드를 실행해보면 5, 4, 3, 2, 1, 끝! 을 출력합니다.

function countdownWithRecursion(num){
    if(num <= 0) {
        console.log("끝!");
        return;
    }
    console.log(num);
    num--;
    countdownWithRecursion(num);
}

countdownWithRecursion(5);

마찬가지로 재귀로 만든 코드도 실행해보면 5, 4, 3, 2, 1, 끝! 을 출력합니다. 재귀 함수를 살펴보면 reutrn을 만나기 전까지 자기 자신을 호출하는 것을 볼 수 있습니다.

두번째 예시

이번에는 팩토리얼을 구현해보겠습니다! 팩토리얼은 값을 1씩 감소하며 1이될때까지 값들을 곱하는 것입니다. 예를 들면 3! 은 321=6이 됩니다.

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

먼저 반복문 예시입니다. for문 안에서 값을 1씩 감소하며 이전 값에 곱해지고 종료점을 만나면 total을 return 해줍니다.

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

다음은 재귀입니다. 두개의 return이 존재합니다. 하나는 상수값 1을 반환하고 하나는 자기자신을 호출하는 코드를 반환하고 있습니다.

1. factorial(3) => return 3 x factorial(2)
2. factorial(2) => return 2 x factorial(1)
3. factorial(1) => return 1

3번에서 자기 자신을 호출하지 않는 return을 반환하고 있으니 종료점이라고 보면 되겠습니다.

그럼 이때까지 구한 값들을 대입시키며 1번까지 돌아가보겠습니다.
4. factorial(2) => reutrn 2 x 1
5. factorial(3) => return 3 x 2
결국 마지막에 반환되는 값은 3x2 즉 6이 되겠습니다.

유의 사항!

또한 앞서 중요한 개념으로 말씀드렸었습니다. 재귀에서는 종료점이 중요합니다.
만약 종료점이 없다면 call stack에 함수가 계속 쌓이게 됩니다. 반드시 return 적절한 값을 reutrn 하도록 재귀 함수를 만들어야합니다.
그렇지 않으면 call stack에 관리해야할 함수가 가득차게되고 Stack Overflow를 초래합니다!

디자인 패턴

재귀 함수를 만들때 자주 사용하는 디자인 패턴이 있습니다.

Helper function

호출하는 함수 내부에 helper 함수를 만드는 방법입니다.
배열과 같은 데이터 목록에서 반복 작업을 해야할 때 사용할 수 있습니다.

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

    function helperFunction(helperInput){
        if(helperInput.length === 0) {
            return;
        }
        
        if(helperInput[0] % 2 !== 0){
            result.push(helperInput[0])
        }
        
        helperFunction(helperInput.slice(1))
    }
    
    helperFunction(arr)

    return result;
}

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

위 예시에서 보듯이 result는 helper함수 밖에서 선언되었습니다.
helper함수 내부에 있다면 helper함수가 실행될때마다 result를 빈 배열로 재할당하기 때문에 result에 데이터를 제대로 담을 수가 없겠죠.

하지만, 배열을 재귀함수 내에서 다룬다고해서 반드시 Helper 함수를 만들 필요는 없습니다. 디자인 패턴 중 하나이기 때문에 개발자에 때라 재귀 함수를 다르게 만들 수 있습니다.