재귀 문제점과 꼬리 재귀와의 함수 비교

재귀함수는 자기 자신을 호출하는 방식으로 다양하게 사용된다.
재귀함수에는 일반재귀와 꼬리 재귀가 있는데 나는 둘 다 사용해온것 같은데 정확한 명칭과 사용방법에 대해서는 제대로 알지 못하는 것 같아 정리하게 되었다.

코드도 짧고 간결한 장점이 있다. 하지만 결국에는 함수를 계속 호출하는 방식이기에 함수가 끝나고 돌아가야할 위치에 대해 스택에 기록된다. 계속 함수가 호출되어 스택 영역의 최대 이상의 크기를 넘어가게 되면 Stack over flow가 발생한다.

편리함을 찾다가 더 위험한 상황이 초래된다. 

그리고 성능적으로도 문제가 있다.
 피보나치 수열의 예시를 확인해보자.

private static int factorial(int n) {
    if (n == 1)
        return n;
    return n * factorial(n - 1);
}

Debug 모드로 확인해보면 stack에 계속해서 메소드 종료후 돌아가야하는 주소값이 계속 쌓이는 걸 볼 수 있다. 

스택 영역 메모리가 초과되면 오버플로우가 발생할 것이다.

컴파일러는 해당영역에 대한 정보를 다음과 같이 해석해서 진행한다.

int factorial(int n) {
  if (n == 1) 
      return 1;
 
  int result = factorial(n - 1);
  return n * result;
}

그럼 이부분을 꼬리 재귀 함수로 바꿔보자.

private static int factorial(int n) {
    return factorialMethod(n, 1);
}
    
private static int factorialMethod(int n, int value) {
    if (n == 1) {
        return value;
    }
    return factorialMethod(n - 1 , value * n);
}

코드를 보면 factorialMethod에서 반환값에서 별도의 작업을 또 진행하지 않고 전달받은 value에 새롭게 계산해서 반환된다.

재귀가 결국에는 느려지는 대표적인 이유는 일을 마치고 돌아왔을 때 해야할 일이 남아있어서 발생되므로 이를 해결함으로써 속도가 확실히 개선이 된다.


컴파일러는 꼬리 재귀로 작성된 문법을 아래와 같이 변경한다. 그렇기 때문에 코드가 최적화 되면서 일반 재귀에서 발생했던 단점을 없애주고 반복문의 형태로 변경해준다. 

결론은 이렇게 컴파일러가 꼬리물기의 문법의 경우 메서드가 종료된 후에 별도의 작업을 진행하지 않는다는 것을 알기 때문에 스택에 호출 주소를 쌓지 않게 된다. 그래서 stack overflow 문제를 해결할 수 있다.

int factorialMethod(int n) {
   int value = 1;
 
   do {
     if (n == 1) 
       return;
     value = value * n;
     n = n - 1;
   } while(true);
}