[JAVA] 꼬리 재귀(Tail Recursion)(꼬리 재귀 최적화(TCO))

일반 재귀 간단 요약
재귀 함수는 정지 조건(재귀 앵커)을 충족하기 전 까지 계속 호출하게 된다. 그러면 함수가 한 번씩 호출될 때마다 파라미터, 리턴값, 리턴 후 돌아갈 위치 등이 스택(메모리 저장공간)에 쌓이게 된다.
재귀 함수를 너무 많이 호출하게 되면 스택의 공간이 모두 차버리는 스택 오버플로가 일어날 수 있다.

 

꼬리 재귀

static int factorial(int n)
{
    if(n > 0) return n * factorial(n-1); //반환(return)부에 연산이 존재
    else return 1; //정지 조건
}

위 코드는 일반 재귀를 이용하여 팩토리얼을 구하는 재귀함수이다.

위 코드는 정지 조건을 충족한 재귀 함수가 1을 리턴을 해야 나머지 재귀 함수의 리턴 값이 정해진다.

아래의 첫 번째 그림은 팩토리얼 메소드에 파라미터 3을 전달했을 때 스택의 모습이고

이를 스택에 쌓여 있는 메소드들을 의인화한 그림은 두 번째 그림이다.

출처 : https://joooing.tistory.com/

출처 : https://joooing.tistory.com/

 

꼬리 재귀는 재귀 함수의 단점을 보완하는 방법 중 하나이다.

꼬리 재귀는 정지 조건을 만난 후 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태이다.

꼬리 재귀의 핵심은 반환(return)부에 연산이 없어야 한다는 점이다.

즉, 정지 조건을 충족한 재귀 함수가 특정 값을 리턴을 해야 나머지 재귀 함수의 리턴 값이 정해져서 결과가 도출되는 것이 아닌, 정지 조건을 충족한 재귀 함수에서 즉시 결과가 도출된다.

static int factorial(int n, int total){
    if(n == 1) return total; //정지 조건 -> 바로 팩토리얼의 값을 리턴
    return factorial(n - 1, n * total);
}

 

위 메소드에 파라미터로 3과 1을 넘기면 메소드들은 아래와 같은 행동을 취한다.

 

출처 : https://joooing.tistory.com/

 

일반 재귀는 스택에 쌓였다가 빠져 나올 때 원래 자기 자리로 돌아가서 앞쪽의 n과 곱해져야 한다(반환(return)부에 연산이 존재). 즉, 리턴 후 돌아갈 위치를 저장하고 있어야 한다는 뜻이다. 위에서 재귀에 대해 설명할 때 스택에 파라미터, 리턴값, 리턴 후 돌아갈 위치 등이 저장된다고 말했었는데, 꼬리 재귀는 리턴 후 돌아갈 위치를 저장할 필요가 없다.

위의 설명을 보고 아래 코드를 보면 일반 재귀와 꼬리 재귀의 차이점을 이해할 수 있다.

static int factorial(int n) //일반 재귀
{
    if(n > 0) return n * factorial(n-1); //반환(return)부에 연산이 존재
    else return 1; //정지 조건
}

static int factorial(int n, int total){ //꼬리 재귀
    if(n == 1) return total; //정지 조건 -> 바로 팩토리얼의 값을 리턴
    return factorial(n - 1, n * total);
}

 

꼬리 재귀를 위한 조건은 아래의 두 가지가 있다.

• 재귀 함수를 꼬리 재귀 방식으로 구현
• 컴파일러가 꼬리 재귀 최적화를 지원

재귀 함수의 스택오버플로우 문제를 해결할 수 있고, 반복문과 성능 차이도 발생시키지 않는다.

꼬리 재귀로 구현된 재귀 함수는 컴파일 시 컴파일러가 꼬리 재귀를 인식하고 최적화하면서 반복문으로 바꿔주기 때문이다.

---

reference : https://joooing.tistory.com/, https://wildeveloperetrain.tistory.com/116