재귀호출 방식의 문제해결 - 2

1. 재귀호출을 이용한 피보나치 수열 구현

0, 1, 1, 2, 3, 5, 8, 13, 21... 로 진행하는 수열을 피보나치 수열(Fibonacci Sequence) 라고 합니다.

제외한 그 이후 F(N) 에 대해서 다음과 같은 일반식으로 표기됩니다.

     

피보나치 관계식은 그보다 큰 문제를 작은 문제 두 개로 나누고 , 각각의 해결책을 합해서

큰 문제의 해결책에 이르고 있습니다.

따라서 재귀호출 하나가 여러 재귀호출의 조합의 형태로 나타도록 구성이 돼야 할 것입니다.

이 관계식을 이용하여 N 번째 피보나치 수열을 구하는 함수는 다음과 같습니다.

int Fibonacci(int n) {     if (n == 0)         return 0;     else if (n == 1)         return 1;     return Fibonacci(n - 1) + Fibonacci(n - 2); }

2. 꼬리재귀

꼬리재귀(Tail Recursion) 란 재귀호출 명령이 함수의 제일 마지막에 오는 것입니다.

또한 호출의 리턴이 수식의 일부여서는 안 됩니다.

예를 들어, 팩토리얼의 리턴 구현부분은 다음과 같습니다.

                return (n * Factorial(n - 1));

     

이 경우 Factorial(n - 1) 의 결과 값이 반환되어서 n 과 곱해질 상황이 남아있습니다.

꼬리재귀의 특성은 재귀호출에서 되돌아오면서 할 일이 전혀 없어야 합니다.

이러한 꼬리재귀의 특성으로 공간적, 시간적 이점을 모두 취할 수 있습니다.

일반적인 재귀의 방식은 활성화 레코드를 쌓아 올립니다.

여기서 활성화 레코드란, 함수의 상태를 복원하기 위한 메모리로서, 함수의 리턴 값, 파라미터,

지역변수, 귀환할 주소 등의 정보가 기록됩니다.

활성화 레코드는 함수 호출 시 사용되는 메모리, 즉 스택 프레임 이라고도 불립니다.

재귀호출이 반복 될수록 활성화 레코드가 함수 호출 수만큼 추가되고, 최종적으로 리턴 될 때

이 메모리 공간이 반환되는 작업까지 수반됩니다.

하지만 꼬리재귀 방식으로 구현된 재귀 호출은, 리턴 시에 하는 작업이 전혀 없기 때문에

굳이 활성화 레코드를 추가로 생성할 필요가 없습니다.

왜냐면 이전 상황을 다시 복구할 필요가 없기 때문입니다.

따라서 꼬리재귀로 구현 한 경우 컴파일러의 도움을 받아서 추가로 활성화 레코드를 할당하는

것이 아니라, 기존의 공간에 덧씌우게(Overwriting) 됩니다.

따라서 별도의 스택 프레임을 할당하는 시간과, 반환하는 시간이 줄어들어서

재귀호출의 가장 큰 단점으로 지적받는 속도의 문제를 해결 할 수 있습니다.

3. 꼬리재귀로 개선한 팩토리얼과 피보나치 수열

int Factorial_Tail(int n) {     return Fac(n - 1, n); }   int Fac(int n,  int iRet) {     if (n == 1)         return iRet;     return Fac(n - 1, iRet * n); }

꼬리재귀 방식이기 때문에 자기 자신을 호출하면서 결과 값을 추가 인자로 넘기고 있습니다.

되돌아오면서 계산하는 과정을 없애기 위함입니다.

int Fibonacci_Tail(int n) {     return Fibo(n, 0, 1); } int Fibo(int n, int left, int right) {     if (0 == n)         return 0;     else if (n == 1)         return right;     else         return Fibo(n - 1, right, right + left); }

마찬가지로 피보나치 수열도 재귀가 일어날 때마다 그 다음 값을 계산하여서 파라미터로 

넘기고 있습니다.

피보나치 수열의 경우 일반 재귀와, 꼬리재귀의 속도차이는 극명합니다.

가령 피보나치 43번째 수열을 구하는 과정을 시간체크 해보았을 때의 결과입니다..

동일한 결과를 출력하는데, 꼬리 재귀는 0에 가까운 속도로 즉시 처리하였고, 일반 재귀는

약 30초가량의 시간이 걸렸습니다.

게임 프로그래머 취업 전문 프로그래밍 학원 어소트락 평생교육원

- by Raimondo