어떤것을 정의할 때 자기자신을 참조하는 것이다.
프로그래밍에서 재귀함수는 자기 자신을 호출하는 함수를 말한다.
반복문으로 작성한 코드는 재귀함수를 이용해 작성할 수 있고
재귀함수로 작성한 코드 역시 반복문으로 작성이 가능하다.
1부터 n 까지의 팩토리얼을 구하는 예제를 작성했다.
let sum = 1;
let target = 10;
for(let i=1; i<=target; i++) {
sum *= i;
};
function factorial(n) {
return n === 1 ? 1 : n * factorial(n - 1);
};
// arrow function
const factorial = (n) => n === 1 ? 1 : n * factorial(n - 1);
다음은 간단한 이 코드의 흐름에 대한 설명이다.
1
을 return 하면2 * 1
을 return 하며 종료 된다.5 \* 4 \* 3 \* 2 \* 1 = 120
과 같다재귀함수를 이용하면 반복문을 사용하지 않아도 반복적으로 실행되는 로직을 작성할 수 있다. 될 수 있으면 반복문 사용을 지양(?)하는 요즘 트렌드에 어울리는 듯
그러나 재귀함수는 계속 자기 자신을 호출하기 때문에 함수가 종료되기 전까지 계속해서 콜스택에 호출한 함수가 계속 쌓이게 된다.
몇 번 호출하고 함수가 종료되면 상관 없지만 예외가 발생해 함수가 종료조건에 도달하지 못하거나, 종료조건이 적절해도 콜스택이 가득 차기 전에 처리를 끝내지 못할 정도로 큰 입력 값이 들어오게 되면 아래처럼 스택오버플로우 에러가 발생할 수 있다.
이에 대한 해결책으로 꼬리재귀 최적화를 이용할 수 있다.
다음은 factorial을 구하는 재귀함수를 꼬리재귀 패턴으로 바꾼 코드이다.
꼬리재귀는 연산에 사용해야할 값을 함수 내에서 처리하지 않고 다음 함수를 호출 시 파라미터로 같이 넘기는 방식이다.
function tailFactorial(n, total = 1) {
return n === 1 ? total : tailFactorial(n - 1, n * total)
}
이런 방법으로 재귀함수를 작성하면 컴파일이 필요한 언어에서는 꼬리재귀 코드를 반복문으로 바꿔주기 때문에 아무리 큰 입력이 들어와도 재귀함수가 스택오버플로우를 일으키지 않게 된다.
자바스크립트를 사용하는 브라우저 환경에선 아직까진 Safari 만이 유일하게 꼬리재귀 최적화를 지원한다고 한다.
위에서 작성한 코드로 실행하면 입력값이 커졌을 때 출력 값이 Infinity 가 나오는 불상사가 발생해 1 부터 N 까지의 합을 구하는 아래의 꼬리재귀 코드로 진행했다.
function tailSum(n, total = 0) {
return n === 0 ? total : tailSum(n - 1, total + n);
};
기기마다 조건이 모두 다르기 때문에, 어떤 환경에서 실행해도 항상 내가 해본 결과와 같은 결과를 얻을 수 있을지 보장하진 못하지만 내가 테스트 해 본 환경은 다음과 같다.
Chrome 브라우저에선 위의 코드 기준 입력 값 약 8371 ~ 8375 이상에서 스택오버플로우 에러가 발생하기 시작한다.
Edge 브라우저 역시 크로미움 기반이기 때문에 크롬과 결과가 같다.
Firefox 브라우저에선 약 14000 ~ 15000 이상의 값에서 스택오버플로우 에러가 발생하기 시작한다. 가용 메모리가 많을수록 조금 여유가 늘어나는 듯하지만 의미 있는 차이는 아닌 거 같다.
Safari 브라우저에선 기기마다 조금 큰 편차가 있는 거 같다. 맥북에서는 약 29200 이상의 값에서 스택오버플로우 에러가 발생하기 시작했는데 아이폰(13 Pro Max 기준)과 아이패드(Pro 12.9 5세대 기준)의 Safari 에서는 약 6170 이상의 값에서 스택오버플로우 에러가 발생하기 시작했다.
그런데 분명 꼬리재귀를 지원한다고 했는데 콜스택에러가 나서 찾아보니 꼬리재귀를 활용하려면 엄격모드에서 실행되어야 한다고 한다. 근데 개발자콘솔에서는 되지 않고 html 파일을 하나 만들고 스크립트를 삽입해야 잘 된다.
실제로 스크립트 상단에 엄격모드를 활성화 한 후 테스트 해보니 어떤 기기든지 아무리 큰 수가 입력으로 들어가도 스택오버플로우 에러가 발생하지 않고 값이 잘 출력되었다.