JS : 꼬리재귀는 일반재귀함수가 가진 메모리,성능 문제를 해결한다.

재귀함수

재귀 함수는 자기 자신을 다시 호출하는 함수이다. 반복문은 항상 재귀함수를 통해 구현 할 수 있고 그 반대도 가능하다.
때로는 복잡한 문제들을 재귀함수 하나로 손쉽게 해결할 수 있다. 문제풀이에서는 DFS를 구현하는 기본적인 방법으로 널리 사용된다.

일반 코드는 순차적으로 실행 흐름을 따라가며 이해할 수 있는 반면, 재귀함수는 코드의 어느 부분에서 어느 부분으로 오고 가는지, 현재 어느 상태에 있는지 파악하기가 어렵다.

• 재귀의 베이스 : 더이상 쪼갤 수 없는 명확한 결과값 제시
• 재귀 단계 : 목표 작업을 위해 재귀의 베이스에 도달할 때 까지 이어지는 동작
• 재귀의 깊이 :
  • 가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수
  • 깊이는 스택에 들어가는 실행 컨텍스트의 수의 최대값과 동일하다.

꼬리재귀

재귀함수는 메모리를 많이 차지하기 때문에 성능이 반복문에 비해 느리다.

함수 호출시 함수의 매개변수, 지역변수, 리턴 값, 종료 후 돌아가는 위치가 스택 메모리에 저장된다.

재귀함수를 사용하면 함수를 반복 호출하므로 스택 메모리가 커지고 호출 횟수가 많아져 스택오버플로우 가 발생한다.

꼬리재귀는 재귀호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않는 재귀의 형태이다. 이는 컴파일러가 선형으로 처리하도록 알고리즘을 바꿔서 스택을 재사용 가능하게 한다.(단 컴파일러가 이 기능을 지원해야 함)

하여튼 결론적으로 꼬리재귀는 위와 같은 재귀함수의 문제를 해결할 수 있는 방법이다.

• 개발자는 꼬리재귀를 이용해야 한다.
• 컴파일러가 꼬리 재귀 최적화를 지원해야 한다.

컴파일러가 꼬리 재귀 최적화를 지원하지 않으면, 개발자가 꼬리 재귀 방식으로 개발해도 성능 및 메모리의 이점을 얻을 수 없다.

다음은 재귀와 꼬리재귀를 사용한 factorial이다.

일반 재귀
function fac(n){
  if(n === 1){
    return n;
  }
  return n*fac(n-1);

꼬리재귀
function fac(n){
  if(n === 1){
    return n;
  }
  let result = fac(n-1);
  return n*result;

단순하게 보면 결과가 같지만 스택창을 확인하면 일반 재귀함수는 스택이 계속 쌓이는 반면, 꼬리재귀는 한번만 호출된다.
단순히 말해서 일반적인 재귀함수는 리턴값이 함수이기 때문에 계속 함수를 호출한다. 하지만 꼬리재귀는 함수를 호출하고 그 함수를 변수에 할당하고 사용한다.
이처럼 함수에서 추가 연산이 일어나지 않는다.

즉 꼬리재귀는 스택이 계속 쌓이는 재귀의 단점을 보완한 것이다.

---

참고자료

https://lygggg.github.io/blog/recursive/

재귀함수란? 간단하게 알아보자.

https://velog.io/@ajt1097/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98-%EB%8D%94-%EC%83%9D%EA%B0%81%ED%95%B4-%EB%B3%BC-%EC%A3%BC%EC%A0%9C

재귀함수