[JS/Node] 꼬리 재귀(Tail recursion in JavsScript)

꼬리 재귀(Tail recursion in JavsScript)

너무 많은 재귀 호출은 메모리 초과 (Stack overflow) 오류를 발생시킬 수 있다.

Tail recursion(꼬리 물기 재귀)은 call stack에 새로운 stack을 생성하지 않고 함수를 참조할 수 있게 한다.

다음 연산에 필요한 값을 다음 루틴에 넘기면 호출당했던 곳으로 돌아와 연산을 거칠 필요가 없어 메모리에 쌓이지 않고 한 번씩만 호출되도록 만드는 형태이다.

많이 사용하는 예제인 factorial 함수를 예로 들어보자.

[일반적인 재귀 코드]

function factorial(n){
    if(!)
        return 1;
    return n*factorial(n-1);
}

위의 코드는 다시 호출 당했던 곳으로 돌아가게 되는 일반적인 재귀 코드이다.

꼬리 재귀가 되기 위해서는, (호출할 함수가 꼬리 위치에 있으려면) 호출된 함수의 반환 값이 호출한 함수에서 반환되는 유일한 값이어야 한다.

factorial(3)을 실행했을 때의 call stack

[Tail recursion]

function factorial(n,partialFactorial=1){
    if(!n)
        return partialFactorial;
    return factorial(n-1,n*partialFactorial)
}

위의 바뀐 코드는 return 되는 재귀함수에 결과를 같이 넣어주었다. 다음 연산에 필요한 값을 다음 루틴에 넘기면, 다시 돌아와 연산을 거치지 않기 때문에 메모리에 쌓이지 않고 한 번씩만 호출이 되는 형태이다.

factorial(3)을 실행했을 때의 call stack

일반적인 재귀와 Tail recurtion의 Execution Context Stack만 비교해봐도 메모리 사용을 더욱 줄일 수 있는 것을 알 수 있다.

하지만, 이런 최적화 지원 기능은 ES6부터 지원되기 시작했고 아직 많은 JS Engine에서 지원하지 않고 있다고 한다. 사파리와 IOS 11.3, 12를 제외하고는 지원되지 않는다고 한다.

언젠가는 많은 브라우저에서 지원을 할 수도 있으니, 미리 연습을 해두는 것도 좋지 않을까..

참고사이트

ECMAScript 6 Proper Tail Calls in WebKit