재귀 함수

목표

재귀의 의미
재귀의 사용 시기
base case와 recursive case에 해당하는 재귀 함수
꼬리재귀함수의 이해

재귀(Recursive Function)

재귀(Recursion)는 자신을 정의할 때 자신을 재참조하는 방법을 의미합니다. 자신을 재참조하는 형태를 재귀 호출(Recursive Call)이라 합니다. 재귀 함수(Recursice Function)는 재귀적으로 자기 자신을 계속 호출하여 작업을 수행하여 문제를 작게 나눠서 답을 도출합니다. 예를 들어, 피보나치수열이나 팩토리얼에서 주로 사용합니다.

재귀적으로 자기 자신을 계속 호출하여 문제를 재귀적으로 작게 나누는 부분을 Recuresive case라고 하고, 더이상 나눌 수 없고 재귀를 탈출하는 부분을 Base Case라고 합니다. Base Case에서 최종적으로 재귀를 탈출합니다.

  // 재귀함수 - Factorial
  function factorial(num){
    // Base Case
    if (n === 1) {
      return 1;
    }
    // Recursive Case
    return n * factorial(num - 1);
  }

재귀적 사고

프로그래밍에서 재귀 함수를 사용해서 풀 수 있는 문제는 모두 반복문을 통해 해결 가능합니다. 즉, 재귀는 반복문과 유사하다고 할 수 있습니다. 반복문은 접근 방식은 익숙해서 금방 접근할 수 있습니다. 그러나 재귀적으로 접근하기 위해서는 재귀적인 사고가 필요합니다.

재귀적으로 문제를 접근하기 위해서는 다음 과정이 필요합니다.

재귀 함수의 입출력 정의
- 무엇을 입력값으로 넣어서 무슨 값을 출력할지 결정하는 단계
문제를 나눌 기준 정의
- 입력값, 순서, 크기에 따라 나눌 기준 정의하는 단계
나눈 문제 해결 - Base Case
- 가장 쉬운 부분을 해결하는 단계
- 재귀함수에 탈출조건을 부여하여 무엇을 출력할지 결정
전체 문제를 작은 문제로 재정의하여 해결 - Recursive Case
- 문제를 더 작은 문제로 새롭게 정의하는 단계
- 재귀적으로 어떤 입력값, 계산을 재참조하는 자신의 함수에 전달할지 결정
코드 구현
- 코드로 재귀함수를 구현하는 단계

재귀함수의 장단점

재귀함수는 변수의 사용을 줄여줄 뿐만 아니라, 동작을 이해하기 쉽다는 장점을 갖습니다. 그러나, 반복문 사용보다 메모리 사용량이 많고 수행 시간이 길어져 큰 오버헤드를 갖습니다. 함수를 계속해서 호출하기 때문에 스택오버플로우(StackOverFlow)도 발생할 가능성이 높습니다. 이외에도 여러 단점이 있는데 주요 장단점을 정리한 표는 다음과 같습니다.

재귀함수의 장점	재귀함수의 단점
- 변수의 사용 감소	- 함수 호출이 많아 StackOverFlow 발생 가능
- 가독성이 좋음	- 확실한 종결조건이 없으면 무한 반복 발생(CPU 크래쉬)
	- 반복문보다 시간복잡도 계산 복잡
	- 반복문보다 메모리 사용량과 수행 시간이 증가(오버헤드 증가)

꼬리 재귀

꼬리 재귀는 재귀 호출 후 추가 연산을 요구하지 않는 구현을 뜻합니다. 꼬리 재귀 함수는 2개 이상으로 분리되어 있어 일반적인 재귀함수와 다르게 콜 스택이 추가적으로 생성되지 않습니다. 그러나 꼬리 재귀 함수를 사용하기 위해서는 컴파일러가 꼬리 재귀 최적화를 지원해야 합니다. (다행히 지금 사용하는 JS는 꼬리 함수 최적화를 지원합니다!)

프로그래밍 언어	지원 여부
C++	지원
C#	지원
JAVA	지원하지 않음
Scala	지원
JavaScript	지원(ES6)
Kotlin	지원
Swift	지원

재귀함수와 꼬리재귀함수 비교

재귀함수와 꼬리재귀함수를 코드로 살펴보면 다음과 같습니다.

  // 일반 재귀함수
  function factorial(num){
    // Base Case
    if (n === 1) {
      return 1;
    }
    // Recursive Case
    return n * factorial(num - 1);
  }

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

위의 코드에서 꼬리 재귀함수를 컴파일러가 해석한 코드는 다음과 같습니다.

function FactorialTail(num){
  let acc = 1;

  while(true){
    if(num === 1){
      return acc;
    }
    acc *= num;
    num -= 1;
  }
}

즉, 꼬리 재귀함수는 컴파일러가 반복문으로 변경하여 실행하여 여러번 호출하던 일반 재귀함수와는 다르게 한번만 호출하게 됩니다.

재귀 함수(Recursive Function) / 꼬리 재귀 함수(Tail Recursive Function)