5.재귀함수

재귀 (Recursion) 함수란 특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결해나가는 함수입니다. 코드가 보다 간결해져 가독성을 높이는 장점이 있지만 함수를 호출하면서 함수의 입력 값, 리턴 값, 돌아갈 위치 값 등을 스택에 저장한다.

재귀 함수를 사용하면 함수가 끝나지 않은 채 계속해서 함수를 호출하므로 스택에 메모리가 쌓이게 되고, 이는 스택 오버 플로우를 일으키는 원인이 될 수도 있다.
예를 들어 피보나치 수열을 재귀함수로 코딩하면

int Factorial(int n)

{

	if (n == 1) return 1;

	return n * Factorial(n-1);

}

에서 n이 커질 수록 스택에 저장해야 할 값이 늘어나 오류가 발생하게 된다.

이를 해결하기 위해서 꼬리 재귀를 사용한다

function factorialTail(n, acc) { //acc: accumulator
  if (n === 1) return acc;
  return factorialTail(n - 1, acc * n); 
//일반 재귀에서의 n * factorial(n - 1)과 달리 반환값에서 추가연산이 필요없음
}
function factorial(n) {
  return factorialTail(n, 1);
}