[javascript] 재귀함수와 꼬리재귀

# 재귀함수

함수가 자기 자신을 호출하는 것을 재귀함수라고 한다. 재귀함수는 종료조건이 있어야 하며, 종료조건을 설정해주지 않으면 무한 반복을 하게된다. 재귀 함수를 사용하는 이유는 알고리즘 자체가 재귀적으로 표현하기 자연스러울 때 혹은 변수 사용을 줄이기 위해 사용한다.

# 재귀함수 사용

일반적인 재귀함수 사용방법이다.

  // 재귀 함수
  function factorial(n) {
    if (n === 1) {
      return 1;
    }
    return n * factorial(n - 1);
  }

  factorial(3); // 6

# 재귀함수 동작 과정

(1) factorial(3) 함수 컨텍스트 생성 -> factorial 호출문 만나면 실행 단계 중지 및 인자로 (2) 전달
(2) factorial(2) 함수 컨텍스트 생성 -> factorial 호출문 만나면 실행 단계 중지 및 인자로 (1) 전달
(3) factorial(1) 함수 컨텍스트 생성 -> n이 1이므로 1 출력 -> factorial(1,6) 함수 컨텍스트 제거
(4) factorial(2) 함수 컨텍스트가 n과 전달받은 호출 결과 1을 연산하여 2 출력 -> factorial(2) 함수 컨텍스트 제거
(5) factorial(3) 함수 컨텍스트가 n과 전달받은 호출 결과 2를 연산하여 6 출력 -> factorial(3) 함수 컨텍스트 제거

# 꼬리재귀 사용

재귀 함수의 단점으로는 콜스택의 부하로 인한 메모리 낭비인데 꼬리 재귀(재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반환되도록 하는 방법)를 통해 해결할 수 있다. 꼬리 재귀를 사용하면 이전 함수의 상태를 유지하지도 않고 추가 연산을 하지도 않아서 콜스택의 부하 문제를 해결할 수 있게 된다.

  // 꼬리 재귀 함수
  function factorial(n, total = 1) {
    if (n === 1) {
      return total;
    }
    return factorial(n - 1, n * total);
  }

  factorial(3); // 6

# 꼬리재귀 동작 과정

(1) factorial(3,1) 함수 컨텍스트 생성 -> factorial 호출문 만나면 실행 단계 중지 및 인자로 (2,3) 전달
(2) factorial(2,3) 함수 컨텍스트 생성 -> factorial 호출문 만나면 실행 단계 중지 및 인자로 (1,6) 전달
(3) factorial(1,6) 함수 컨텍스트 생성 -> n이 1이므로 파라미터로 전달받은 total 변수의 값인 6 출력 -> factorial(1,6) 함수 컨텍스트 제거
(4) factorial(2,3) 함수 컨텍스트가 전달받은 호출 결과 6 출력 -> factorial(2,3) 함수 컨텍스트 제거
(5) factorial(3,1) 함수 컨텍스트가 전달받은 호출 결과 6 출력 -> factorial(3,1) 함수 컨텍스트 제거

위와 같이 재귀함수의 경우 전달받은 호출 값을 사용하여 연산을 진행하게 되는 반면 꼬리재귀는 전달받은 호출 값을 그대로 사용하게 된다. 위와 같은 동작 과정에서도 알 수 있듯이 매번 연산을 진행하는 재귀함수의 문제를 마지막 한번에 출력 값을 활용하는 꼬리재귀를 통해 해결할 수 있게 된다.