재귀함수

재귀 함수는 자신을 계속 재호출 하는 함수를 말한다. 자기 자신을 호출하므로써 반복문과 같은 효과를 낼 수 있다. 따라서 재귀함수로 해결할 수 있는 문제는 반복문으로도 해결할 수 있고 그 역도 성립한다.

반복문과 재귀 함수

재귀 함수는 반복문과 비교하는 과정에서 이해할 수 있다.

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

function factorial(num){
  if (num === 1) return 1
  return num * factorial(num-1)
}

위 함수들은 각각 반복문과 재귀함수를 이용하여 factorial을 계산하는 함수들이다. 기능은 같으나 그 구조가 다른데 반복문과 비교해서 재귀 함수가 유리한 면은
1. 일단 눈에 보이는 재귀함수가 가지는 이득은 더 적은 변수를 사용한다는 것이다.
2.또 코드의 길이가 짧고 복잡한 상황일수록 가독성이 높은 코드로 작성이 가능하게 도와준다.

하지만 재귀함수가 갖는 단점도 있다.
1. 재귀 함수는 자신을 재호출 하는 구조를 갖다보니, 종료 조건을 만나기 전까지 호출된 자기 자신(재귀함수)이 queue에 쌓여있게 된다. 이를 stack이라고 하는데 이 대기열이 너무 많아지면 stack의 size를 벗어나게 되고 오류를 발생시킨다. (이를 stack overflow라고 한다)
2. 표면적인 함수의 모습으로는 더 많은 변수들을 사용하고 관리하는 반복문의 속도가 더 느려보이지만 재귀 함수는 안보이는 곳에서 stack을 관리하는 과정에서 반복문보다 더 큰 overhead를 발생시키기 때문에 일반적으로 재귀함수가 더 느리다.

꼬리재귀 (taril call recursion)

위와 같은 재귀함수의 단점을 보완하기 위해 꼬리 재귀라는 방법을 사용한다.

function factorial(num, result =1){
  if (num === 1) return result
  return factorial(num-1, num*result)
}

위 재귀 함수와 비교해 return값이 달라졌는데 이는 함수의 return 값에 연산을 주지 않기 위한 방법이다.
이런식으로 재귀함수를 작성하게 되면 꼬리재귀 최적화를 지원하는 컴파일러가 적당한 반복문으로 바꿔 실행하기 때문에 stackoverflow나 overhead에서 오는 단점을 보완할 수 있게 된다.

결론

단순히 반복문과 비교해 보면 재귀함수의 효용이 커보이지 않는다. 컴파일러까지 도와가며 반복문으로 바꿔 실행할거면 애초에 왜 재귀함수를 써야 되나 하는 의문이 들 수 있다. 성능 측면에서만 보면 반복문의 기능이 더 크기 때문이다. 하지만 재귀 함수가 갖는 장점은 생각보다 더 크다고 볼 수 있다. 개발자가 관리하는 변수가 적다는 것은 mutable state가 작다는 의미이므로 실수를 줄일 수 있으며 가독성이 좋다는 것은 특히 협업에서 큰 이득이 된다. 따라서 재귀함수 용법도 익혀 반복문과 때에 따라 판단하여 사용할 수 있어야 한다.