꼬리 재귀(Tail recursion)

꼬리 재귀(Tail recursion)는 간단하다. 재귀 함수의 단점으로 인해 반복문을 사용하는 상황을 피할 수 있는 방법 중 하나인데, 너무 많은 재귀 호출로 인해 메모리 초과(Stack overflow) 오류가 발생 할 수 있다. 꼬리 재귀를 통해 콜 스텍(call stack)에 새로운 스텍을 생성하지 않고 함수를 참조할 수 있게 한다.
다음 연산에 필요한 값을 다음 루틴에 넘기면 호출 당했던 곳으로 돌아와 연산을 거칠 필요가 없어 메모리가 쌓이지 않고 한번씩 호출되도록 만드는 형태이다.

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

일반적인 재귀 함수 factorial(3) 의 실행 결과

이 전 재귀함수에서 사용했던 팩토리얼 예제를 보면 호출 당했던 곳으로 다시 돌아가게 되는 일반적인 재귀 코드이다.
꼬리 재귀가 되기 위해서는 호출된 함수의 반환값이 호출한 함수에서 반환되는 유일한 값이여야만 한다.

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

위 코드는 return 되는 재귀 함수에 결과를 같이 넣어준 코드이다. 다음 연산에 필요한 값을 다음 로직에 넘기면, 다시 돌아와 연산을 거치지 않기 때문에 메모리에 쌓이지 않고 한번만 호출되는 형태인 것이다.
또는

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

또 다른 표현으로는 partialFactorial 변수를 함수 내부에 선언해 변수의 값으로 factorial() 함수를 직접 넣어 한번의 로직으로 연산을 마치는 과정이다. 이렇게해도 위의 코드와 같이 꼬리 재귀로서 역할을 할 수 있고 똑같이 메모리에 쌓이는 과정 없이 한번만 호출되는 형태가 되는 것이다.

꼬리 재귀 factorial(3) 의 실행 결과

일반적인 재귀 함수와 꼬리 재귀의 콜 스텍만 비교해봐도 메모리 사용을 더욱 줄일 수 있는 것을 알 수 있다. 현재는 지원하는 브라우저가 매우 한정되어 있다는 단점이 있다. 현재 브라우저 중 꼬리 재귀 최적화를 지원하는 브라우저는 이 곳에서 확인 할 수 있다.
하지만 Javascript에서 ES6 스펙에 tail calls optimisation 을 지원한다고 명시하고 있고, 꼬리 재귀를 사용하였을 경우의 Chrome65에서 약 17배의 속도 향상을 한다고 나와있기 때문에, 앞으로 더 많은 웹 브라우저가 꼬리 재귀를 지원하게 될 것을 대비하여 미리 익혀두는 것이 좋겠다.