[Javascript] 재귀 함수의 스택 오버플로우 문제

Development/Javascript

[Javascript] 재귀 함수의 스택 오버플로우 문제

highcastlee 2022. 6. 14. 22:35

n!을 구하기 위한 factorial(n) 함수를 재귀 함수로 구현한 상황에서 n 값이 매우 클 때 발생할 수 있는 문제는?

Factorial 함수

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


factorial(4);  // 4*3*2*1 => 24

[문제 1] 숫자 값이 너무 크면 표현할 수 있는 int의 범위를 넘어설 수 있다.

20! = 20×19×18×...×2×1 = 2,432,902,008,176,640,000
factorial(n)의 n이 20이 되어도 엄청 큰 수가 나온다.

Number 타입은 배정밀도 64비트 이진 형식 IEEE 754 값(-(2^53 − 1)부터 2^53 − 1까지의 수)이다. Number 타입은 부동소수점 숫자 외에도 +Infinity, -Infinity, NaN("Not a Number") 세 개의 상징적인 값을 가진다. (참고)

ECMAScript 2015부터는 Number.isSafeInteger()와 Number.MAX_SAFE_INTEGER 및 Number.MIN_SAFE_INTEGER를 사용하여 숫자가 배정밀도 부동 소수점 숫자 범위 안에 있는지 확인할 수도 있다. 이 범위를 넘어서면 JavaScript의 정수는 더 이상 안전하지 않으며, 그 값의 배정밀도 부동 소수점 근삿값이 된다.

즉, Number 타입의 범위를 넘어서면 정확한 값을 구할 수 없다.

[해결 1] BigInt 타입을 사용하여 Number 범위 문제를 해결한다.

BigInt는 정수 끝에 n을 추가하거나 생성자를 호출해 생성할 수 있다.

Number 타입의 안전 한계는 Number.MAX_SAFE_INTEGER로 알아볼 수 있는데, BigInt의 도입 이후로는 이 한계를 넘는 숫자에 대해 계산이 가능하다.

> const x = 2n ** 53n;
9007199254740992n
> const y = x + 1n;
9007199254740993n

[문제 2] 재귀 함수의 반복 호출로 스택 오버플로우가 발생할 수 있다.

함수가 실행되면, 개별적인 함수 실행 컨텍스트를 콜 스택에 쌓아 차례대로 실행되는데, 함수가 호출되면 함수의 지역변수, 매개변수, 리턴 후 돌아갈 위치, 리턴 값 등을 스택에 저장하기 때문에 너무 많은 재귀 함수의 호출은 스택 오버플로우를 발생시킨다.

[해결 2] 꼬리 재귀(tail call recursion) 기법 활용

재귀 함수의 문제는 자기 자신인 함수를 호출한 뒤 그 결과를 기다리면서 생기는 콜스택 메모리 낭비였는데, 꼬리 재귀라는 개념을 이용하면 재귀 호출이 끝나는 시점에 바로 결과를 반환하도록 하여 오버 플로우를 방지할 수 있다. 다만, 꼬리 재귀 기법은 언어 수준에서 꼬리 재귀 최적화를 지원해야한다는 특징이 있다.

꼬리 재귀 최적화 (TCO : Tail Call Optimization)

꼬리 재귀 최적화는 컴파일러 or 인터프리터 수준에서 지원해야한다. 즉, 기존의 방식과는 다르게 꼬리 재귀인 상황에서는 최적화하여 동작하도록 만들어 놓은 것이다.

일반 재귀는 함수가 호출될 때마다 return address, arguments, local variables 등의 메모리를 할당하여 stack에 쌓인다. 꼬리 재귀 최적화는 return 부분에서 연산 없이 재귀로 호출된다면 위의 메모리를 추가로 생성하는 것이 아닌, 기존의 메모리를 사용하여 반환함으로써 메모리 낭비를 줄이는 것이다.

factorial 예제에서 꼬리 재귀의 핵심은 반환부에 n * factorial(n-1) 같은 연산이 없어야 한다는 것이다. factorial 예제를 꼬리 재귀로 표현하면 다음과 같다.

// 일반 재귀
function factorial(n){
  return n <= 1 ? 1 : n*factorial(n-1);
}

// 꼬리 재귀
// JS 스펙 상, 삼항 연산자는 스택의 메모리를 잡아 먹지 않는 연산자다.
function factorial(n){
  const cal = (n, result) => {
    return n <= 1 ? result : cal(n-1, n*result);
  }
  return cal(n, 1);
}

result가 1부터 시작하여 재귀를 통해 첫 번째 인수인 n을 곱하여 cal이 호출될수록 점점 커지게 된다. 마지막 재귀 함수에서 cal함수의 n이 1이 되었을 때, 누적 계산된 result를 반환하고, 그 반환된 result를 다시 반환하여 최종 factorial 함수가 원하는 값을 반환하는 방식이다.

javascript는 ES6부터 지원을 했지만, 아직 이를 브라우저에 적용하고 있는 js 엔진은 Safari의 Webkit 뿐인 것으로 알려져 있다.

본문에서는 재귀 함수에 대한 문제를 다루었다. 같은 요구사항도 여러 방식으로 구현될 수 있는데, 굳이 재귀를 사용해야하는 조건의 개발 환경은 주어지지 않을 것이다. 유지보수성보다 우선되어야할 것이 에러 가능성을 줄이는 것이므로, 콜스택 오버플로우가 발생할 가능성이 있을 정도의 요구사항이라면, 반복문을 통해 구현하는 것이 조금 더 안전한 개발이라고 생각한다.