9 - 쉬어가기(재귀함수)

재귀 함수 (Recursive Function)

재귀(Recursion) 에 따라서 내가 나를 호출하여 사용하는 함수라고 볼수 있다.

1개의 함수

void Recursive_fnc() 라는 함수에서 또 다시 자기 자신을 불러서 수행하는 방식을 말한다. 

그렇기 떄문에 재귀 함수 설계시에는 적절한 종료 조건을 만들어서 종료 할수 있도록 설계하고 구현 하여야 한다.

LISP 라는 언어는 재귀를 정말 밥먹듯이 쓴다고 한다. 여기서 따로 언급은 하지 않겠다.

필자는 이제까지 재귀 함수 는 왜 쓰는 걸까? 라고 하게 되면

C에서 속도가 빠르니까 ! 재귀가 속도가 빨라

하지만 Function Call 을 계속 해주기 때문에 아무리 Return 을 한다 해도 메모리상에 자꾸 참조되는 함수가 생기고 언제 

Seg Fault 가 날수 있기 때문에 매우 위험하다라는 생각을 가지고 있었다. 이건 단순한 자료조사가 아닌 카더라 통신과 

주관적인 생각이였을 뿐

갑자기 생각난 재귀함수에 대해서 어떠한 원리일까를 찾아 보던중 재미난 글을 발견 하였다. 

재귀의 가장 큰예는 팩토리얼 함수를 예로 들수가 있다. 1 ~ n 까지 곱하는 것

int factorial (int n)

{

if(n==0) return 1;

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

}

정말 깔끔하며 가독성도 매우 높다. 하지만 이 재귀함수에는 문제점이 있습니다.

매번 함수마다 자기 자신을 호출한다는 점

1. 재귀적으로 함수를 지속적으로 호출시에 fac의 예를 들었을때 

return (n*factorial(n-1)); 이란느 부분이 있는데

만약에

100이라는 값이 들어오게 되면

factorial(100) * factorial(99) * factorial(98) ~.... 으로 1이 되어서 끝나기직전까지 호출만 이루어지는 상황이 발생하는데

함수 호출시 프로세스는 parameter, return values 등이 반환시에 되돌아갈 위치를 스택에 저장하게 되는데

지속적으로 많은 호출이 나타나게되면 스택에 부모함수부터 데이터들을 쌓아 놓게 되는데 스택같은 경우는 무한정으로 

존재하지 않기 때문애 넘치는 Stack OverFlow가 발생할수 있습니다.

팩토리얼같은 경우는 어차피 컴퓨터가 처리하는 수의 범위를 넘어 버리기 때문에 불가능합니다.

2. 또한 스택에 데이터를 자꾸 존재한다는 것은 메모리의 사용량이 증가 된다는 뜻이 되며 

스택에 데이터를 쌓을때 이 값을 복사하게 되는데 이 쯤에서 다시 문제가 생기게 된다. 

피보나치 수열을 예로 들어 보게 되면

F(n+2) = F(n+1) + F(n) 

unsigned int fibonacci(int n)

{

if(n==0) return 0;

else if(n==1) return 1;

else return (fibonacci(n-1)+ fibonacci(n-2));

}

// 재귀 함수의 호출 시간 스크랩 - http://www.nicklib.com/application/2953

보시는거와 같이 2개의 자식 함수를 재귀적으로 부르고 있으며 해당 함수에 대한 시간 입니다.

------------------------------------------------

 N        결과값            걸린시간

------------------------------------------------

10           55                      2마이크로초

20         6765                    225마이크로초

30       832040             34밀리 391마이크로초

40    102334155        3초 544밀리 659마이크로초

50  12586269025   7분 15초  68밀리 740마이크로초

60 1548008755920 14시간 40분 28초 531밀리 693마이크로초

N이 30일경우에는 1초도 걸리지 않기 때문에 괜찮지만 40부터는 눈에 띄게 계산에 대한 시간이 보여지는 것을 알 수 있습니다.

해당 참조하였던 블로거는 n이 50인 값부터 int64으로 변환하여서 돌렸다고 합니다.

60에서 14시간이 걸린것을 보면 오래걸린건지 아닌지 분간이 잘 되지않지만 이 계산법에 대한 코드를

비재귀 함수로 구현하였을때의 속도를 비교하게 되면 재귀의 문제점을 파악할 수 있습니다.

비재귀 함수인

unsigned int fibonacci2(int n)

{

unsigned int a =1, b=1, c=1;

int (n==0) return 0;

for(;n;2;n--)

{

c=a+b;

a=b;

b=c;

}

return c;

}

재귀에 비하여 확실히 복잡하긴 합니다.  해당 소스에 대한 재귀 결과입니다.

<br />

------------------------------------------------

 N               결과값            걸린시간

------------------------------------------------

10                    55             0초

20                  6765             0초

30                832040             0초

40             102334155             0초

50           12586269025             0초

60         1548008755920             0초

70       190392490709135             0초

80     23416728348467685             0초

90   2880067194370816120             0초

100  3736710778780434371             0초

-----------------------------------------------

재귀함수에 대한 문제점을 파악할수 가 있는 결과입니다. 해당 테스트 블로거의 PC의 CPU 사양은 듀얼코어 1.8인 것을 감안하면(고사양은 아님)

엄청난 차이라고 할수 있습니다.

언제나 재귀함수에 대해 검색하면 스택 오버플로우 메모리문제, 속도 문제 등이 나타나는데 절대 안좋은점만이 있는 것은 아닙니다. 

안좋기만한 함수가 왜구현되고 왜 사용되고 재귀함수라는 말이 생겨나고 꼭 프로그래밍 책에 나오는 이유가 있습니다.

보시면 알겠지만 가독성이 매우 뛰어나게 됩니다. 재귀에 대한 다른 이야기는 다음에 찾아서 써보도록 하겠습니다.