꼬리재귀호출 (Tail Recursion)

재귀 호출이란?

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다.

코드가 짧아져 가독성을 높일 수 있다는 장점이 있지만, 스택 오버 플로우를 일으킬 수 있다.

함수를 호출할 때 함수의 입력 값, 리턴 값, 돌아갈 위치 값 등을 스택에 저장한다.

재귀 함수를 사용하면 함수가 끝나지 않은 채 계속해서 함수를 호출하므로 스택에 메모리가 쌓이게 되고,

오버플로우가 발생하는 것이다.

이러한 재귀 호출의 단점을 보완하기 위한 방법으로 꼬리 재귀라는 방법이 있다.

꼬리재귀호출이란?

재귀호출이 끝난 후, 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태이다.

이를 이용하면 함수 호출이 반복되어 스택이 깊어지는 문제를 컴파일러가 선형으로

처리하도록 바꿔 스택을 재사용할 수 있게 된다.

재귀함수 예제

팩토리얼을 재귀함수로 구현한 코드

int Factorial(int n)

{

if (n == 1) return 1;

return n * Factorial(n-1);

}

 컴파일러는 이 코드를 다음과 같이 해석한다

int Factorial(int n)

{

if (n == 1) return 1;

int result = Factorial(n - 1);

return n * result;

}

꼬리재귀로 보완한 코드

int FactorialTail(int n, int acc)    // acc : accumulator의 약자

{

if (n == 1) return acc;

return FactorialTail(n - 1, acc * n);    //  일반 재귀에서의 n * Factorial(n-1)와 달리 반환값에서 추가 연산을 필요로 하지 않음

}

int Factorial(int n)

{

return FactorialTail(n, 1);

}

이와같은 특징을 가진 꼬리 재귀함수를 컴파일러는 다음과 같이 해석합니다.

 int FactorialTail(int n)

{

int acc = 1;

do

{

if (n == 1) return;

acc = acc * n;

n = n - 1;

} while (true);

}

※ 참조 :

https://namu.wiki/w/재귀함수

http://bozeury.tistory.com/entry/꼬리-재귀-최적화Tail-Recursion