[JavaScript] 재귀함수 vs 반복문

알고리즘 공부를 하다보면 재귀함수를 사용하는 경우도 있고, 반복문을 사용하는 경우도 있다. 

사용하는 것에는 문제가 없지만 그 둘의 차이가 무엇일까? 

 

재귀함수 vs 반복문

재귀함수는 자기 자신을 호출해는 함수이고, 반복문은 특정 수만큼 반복한다. 

일반적으로 반복문이 실행 속도는 더 빠르다. 

 

그 이유는 재귀함수의 경우 매개변수, 리턴값, 리턴 시 돌아가야 하는 위치 등의 정보가 

스택에 저장되지만 반복문의 경우 그러한 오버헤드가 없다. 

 

그렇다면 굳이 재귀함수를 사용하는 이유가 무엇일까? 

재귀함수는 반복문에 비해서 속도가 느리다는 단점이 있으니, 전부 반복문을 사용해서 

해결해도 된다. 

 

하지만 그래도 재귀함수를 사용하는 사람이 있다. 그 이유는 뭘까? 

그 이유는 알고리즘을 해결할 때 재귀 함수로 표현하면 더 자연스러워서 가독성이 좋다. 

또한 재귀함수를 사용하면 변수 사용을 줄여줄 수 있다. 

function factorial (number) {
  let result = 1;
  for(let i = 0; i <= number; i++) {
    result *= i
  }
  
  return result
}

우리가 반복문을 사용해서 factorial을 만든다면 이런 방식으로 만들 것이다. 

함수에서 result, i 라는 변수를 사용하고 있다. 

 

function factorial (number) {
  if(number === 1) return 1;
  return n * factorial(n - 1);
}

재귀함수로 만든다면 간결하게 코드를 작성할 수 있다. 

 

꼬리 재귀

재귀 함수로 구현하는데, 비교적 적은 오버헤드를 만들고 싶다면 꼬리 재귀라는 방법이 있다. 

function factorial (number, result = 1;) {
  if(number === 1) return result;
  return factorial(n - 1, n * n - 1);
}

앞서 만든 재귀함수를 수정했다. 

무엇이 달라졌냐면, 재귀 함수를 호출 한 다음 추가적인 연산을 하지 않았다. 

 

재귀함수의 오버헤드에는 매개변수, 리턴 값, 리턴 시 돌아가야하는 위치 등이 있다고 했는데, 

재귀 함수를 호출한 다음 추가적인 연산을 하지 않는다면 리턴 시 돌아가야 하는 위치를 

스택에 가지고 있지 않아도 된다는 장점이 있다. 

 

이러한 방법으로 재귀 함수를 최적화할 수 있지만, 

그렇다고 재귀함수를 무한정 사용할 수 있다는 것이 아닌, 최적화를 했다는 것이고 여전히 

재귀함수를 많이 호출하면 Call stack max 에러는 발생한다.