재귀함수에 대하여

여름노래불러줘·2022년 7월 13일

재귀란?

어떤것을 정의할 때 자기자신을 참조하는 것이다.
프로그래밍에서 재귀함수는 자기 자신을 호출하는 함수를 말한다.

반복문으로 작성한 코드는 재귀함수를 이용해 작성할 수 있고
재귀함수로 작성한 코드 역시 반복문으로 작성이 가능하다.

팩토리얼 구하기

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회 n의 입력 값으로 5 를 넣었을 때
n이 1인지 검사해서
1이 아니면 n-1 (=4) 의 값으로 함수를 다시 호출한다.
n이 1일 때까지 2~3을 반복하다가
마침내 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);
};

기기마다 조건이 모두 다르기 때문에, 어떤 환경에서 실행해도 항상 내가 해본 결과와 같은 결과를 얻을 수 있을지 보장하진 못하지만 내가 테스트 해 본 환경은 다음과 같다.

16GB 메모리 MacOS
16GB 메모리 Windows 운영체제
32GB 메모리 Windows 운영체제
아이패드 프로 12.9 5세대 (Safari 한정)
아이폰 13 Pro Max (Safari 한정)

Chrome 브라우저에선 위의 코드 기준 입력 값 약 8371 ~ 8375 이상에서 스택오버플로우 에러가 발생하기 시작한다.
Edge 브라우저 역시 크로미움 기반이기 때문에 크롬과 결과가 같다.
Firefox 브라우저에선 약 14000 ~ 15000 이상의 값에서 스택오버플로우 에러가 발생하기 시작한다. 가용 메모리가 많을수록 조금 여유가 늘어나는 듯하지만 의미 있는 차이는 아닌 거 같다.
Safari 브라우저에선 기기마다 조금 큰 편차가 있는 거 같다. 맥북에서는 약 29200 이상의 값에서 스택오버플로우 에러가 발생하기 시작했는데 아이폰(13 Pro Max 기준)과 아이패드(Pro 12.9 5세대 기준)의 Safari 에서는 약 6170 이상의 값에서 스택오버플로우 에러가 발생하기 시작했다.