메뉴 건너뛰기


Developer > Application

C,C++ 재귀(recusion)함수의 Overhead

2013.12.28 03:16

푸우 조회 수:27490

이전에 이진트리(Binary Tree)의 순회를 재귀(recusive)방식에서 반복(iterative)방식으로 구현하는 것에 대해 글을 썼던 적이 있습니다.
 
그때 반복방식으로 구현했던 이유를 단순히 Stack Overflow가 나서라고 했었는데...
설득력이 부족한 듯 해서... 이번에는 재귀함수를 사용할 경우의 문제점들을 집어보려고 합니다.
 
우리는 답을 얻기 위한 어떤 큰문제를 작은 부분으로 쪼갤 수 있다면 그 작은 부분들을 해결해 나가면서 결국은 큰 문제를 풀 수 있다는 것을 잘 알고 있습니다. 재귀함수의 원리가 여기에 있겠죠.
사람이 어떤 문제를 해결하는 방법과 유사하기 때문에 위에서 이야기 한 유형의 문제들은 쉽게 재귀함수화 할 수 있고 이런류의 문제를 재귀함수로 만들면 코드 해석도 쉽고 보기에도 깔끔하고 좋습니다.
 
재귀적 문제의 대표적인 예로 팩토리얼(factorial)을 들 수 있습니다.
1부터 n까지를 곱하는 거죠.
코드로 보면 다음과 같습니다.
 
int factorial(int n) { if(n<=0) return 1; return (n*factorial(n-1)); }
 
이야기 한대로 깔끔하고 보기도 좋습니다.
 
 
이 보기도 좋고 해석도 쉬운 재귀함수에도 문제점이 있습니다.
모두 함수를 계속해서 호출하는데 기인한 것인데요.
 
1. 스택 오버플로우
 
함수를 호출할때 프로세스는 입력매변수들, 리턴값 그리고 리턴 됐을 때 되돌아갈 위치를 스텍에 저장을 하게 됩니다.
 
재귀함수는 특성상 부분 문제의 해결이 끝나지 않으면 상위의 문제들도 계속 풀리지 않는데요.
즉, 재귀적으로 호출한 자식함수(?)가 리턴하지 않으면 부모함수(?)도 계속해서 남아있는 거죠.
(부호함수와 자식함수라는 말이 맞을 지는 모르나 이해하기는 쉬울 듯 하여 사용하겠습니다.)
그렇다가 보니 재귀적으로 함수를 호출하면 스텍에 부모함수부터 제일 작은 문제의 풀 자식함수 까지 위에서 이야기한 데이터들을 쌓아 놓게 됩니다. (이를 재귀호출의 감기단계라고 합니다.)
 
아시다시피 스텍은 유한해서 스텍에 값을 계속해서 쌓다가 보면 넘칠 수 있습니다. 이게 Stack Overflow죠. 뭐 위와 같이 함수가 한번만 재귀함수를 호출할 경우는 상당히 많은 호출을 할 수 있습니다. 왜냐하면 스텍의 사용이 n에 선형적으로 증가하기 때문이죠. (사실 위에 제시한 팩토리얼 문제는 값을 곱하기 때문에 쉽게 컴퓨터가 처리할 수 있는 수의 범위를 넘어버립니다. 그래서 n을 크게 주지도 못하죠.)
 
2. 성능의 저하
 
스택에 데이터를 많이 쌓는다는 것은 메모리의 사용량이 증가한다는 것이고...
스택에 데이터를 쌓을 때 이 값을 복사를 하게 되는데요.
반복함수에서는 하나의 변수에서 계산된 값만 유지를 하면되는데 재귀함수로 만들면 입력값도 복사하고 리턴된 결과값도 복사하는 식의 오버헤드가 생깁니다.
요즘같이 메모리를 많이 꽂아 쓰는 시대에서는 메모리를 많이 사용하게 되어 발생하는 문제보다는 함수가 새로 호출되면 CPU가 해당 쓰레드(혹은 프로세스)에 할당한 자원을 빼앗아 버린다는게 더 문제일 수도 있을 것 같습니다.
 
그럼 이제 실제 테스트를 해보도록 하죠.
이번에는 재귀함수 이야기 나오면서 꼭 나오는 피보나치 수열의 계산입니다.
피보나치 수열은 다음과 같이 수학적으로 정의 할 수 있죠.
정의 자체가 딱 재귀함수 모양이네요.
 
F(0)=1, F(1)=1
F(n+2)=F(n+1)+F(n)  (단, n은 0이상의 정수)
 
이를 코드로 만들어 내면 다음과 같습니다.
 
unsigned int fibonacci(int n) { if(n<=0) return 0; else if(n==1) return 1; else return (fibonacci(n-1)+fibonacci(n-2)); }
 
위에서 봤던 팩토리얼의 문제와는 달리 하나의 함수에서 2개의 자식함수를 재귀적으로 호출하고 있습니다. 팩토리얼은 함수의 호출이 n에 대해 선형적으로 증가했던 것에 반해 지수적으로 증가한다는 것을 알 수 있습니다.
 
제가 돌려본 바로는 다음과 같은 시간이 걸렸습니다.
------------------------------------------------ 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초도 안걸렸으니깐... 괜찮은데...
n이 40이 넘어가면 엄청난 시간이 걸림을 알 수 있습니다.
물런 n이 50인 값부터는 int형으로 계산 할 수 없기에 저는 int64형으로 바꿔서 돌렸습니다.
60까지는 돌려봤는데... 그 다음부터는 엄두가 안나서 돌리지 않았습니다.
 
그럼 이 함수를 반복함수로 만들어서 테스트 해 보죠.
코드는 다음과 같습니다.
 
unsigned int fibonacci2(int n) { unsigned int a=1, b=1, c=1; if(n<=0) return 0; for(; n>2; n--) { c=a+b; a=b; b=c; } return c; }
 
 
반복 함수가 훨씬 복잡하기는 하네요. (여기서 한가지... 아무리 알고리즘 책을 찾아봐도 피보나치 수열을 반복함수로 구현한 소스가 없더군요... 제가 가지고 있는 책이 별로인지... 여러분 책에 혹시 피보나치 수열의 반복함수가 나와있다면 좀 올려주세요. 아무튼 여기서는 제가 짠 소스를 가지고 테스트 하겠습니다.)
 
위의 소스를 돌린 결과는 다음과 같습니다. 역시 테스트는 대수를 다뤄야 하기 때문에 64비트 정수형을 다룰 수 있도록 소스를 약간 수정해서 돌린 결과 입니다.
 
------------------------------------------------ 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초 ------------------------------------------------
 
n의 값을 110을 주면 64비트 정수가 표현할 수 있는 값을 넘어서서 더는 못한 거구요.
걸린시간은 제가 측정을 안해서 안적은게 아니구요.
시간을 젤수 없을 정도로 빠르게 계산을 합니다.
제가 측정하는 시간이 마이크로초 단위인데... (즉, 1마이크로초도 안잡힙니다. 제 컴퓨터가 인텔 듀얼코어 1.80GHz인데... 넘 좋은건가요? ㅎㅎ)
 
어때요? 엄청난 차이 아닌가요?
위의 코드에서 unsigned int 를 __int64로 바꿔서 여러분도 직접 돌려 보세요.
 
 
3. 결론
 
제가 지금까지 한 이야기 논조로는 재귀함수는 나쁘니 쓰면 안된다는 거네요.
 
하지만 쓰지마라는 이야기는 아니며 알고 쓰자는 거죠.
 
재귀함수의 깔끔함과 명료함도 장점이라면 장점이니깐... 성능이 그리 중요하지 않은 프로그램에서는 충분히 사용할만 하구요.
n의 값이 그리 크지않을 것이 예상되는 함수인 경우는 그리 많은 차이가 나지 않으니깐 또 사용할 만 하구요.
마지막으로 재귀호출을 하면서 그냥 리턴해버리는 재귀함수(이를 꼬리재귀함수라고 함)인 경우는 감는 과정은 필요하나 푸는 과정은 실제로 필요없기 때문에 요즘 나온 향상된 컴파일러들은 이런 꼬리 재귀함수를 자동으로 감지하여 마치 반복함수처럼 처리하도록 하기도 한다고 합니다.
 
자 어찌되었건... 재귀 함수 쓸땐 쓰더라도 알고 사용합시다.
 
  
Creative Commons License
Creative Commons License이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
Copyright 조희창(Nicholas Jo). Some rights reserved. http://bbs.nicklib.com


아래는 과거 게시판에서 댓글로 달린 내용입니다.

보관의 가치가 있어 댓글도 같이 옮깁니다.



실용프로그… 09-03-13 12:27
  
모든 재귀를 비재귀로 작성이 불가능한 것도 아니며 
모든 프로그램이 성능을 최우선으로 하는 것도 아니다. 

실용 전산에서는 프로그램 목적에 따라 성능과 개발 비용에 대한 적절한 타협을 해야 한다. 
만약 성능만을 따진다면 왜 OOP를 사용하겠는가?  직접 멤버에 접근하면 될 것을 왜 public 메소드나 인터페이스를 거쳐서 가야 하는가?  이 또한 스택이 쓸 데 없이 늘어나고 필요없이 인자가 넘어가는 것이라 할 것인가? 

시스템 프로그램과 같이 성능과 신뢰성, 유지보수 측면을 같이 생각해야 하는 분야를 제외하면 

작금에 와서 프로젝트에서 대부분 인건비가 제일 중요한 요소임에 틀림이 없다.  그리고 대부분의 인건비는 유지보수 
때문에 발생한다고 해도 과언이 아니다.  이는 H/W의 비약적인 발전이 한 몫을 하였다. 

실력이 있는 엔지니어가 재귀로 하는 것보다 비재귀로 하는 것이 좋다라는 이상적인 생각으로 프로그래밍을 한 것을 이후 후임자가 분석을 한다고 하면 역시 재귀로 작성된 것에 비해 가독성이 떨어질 수 밖에 없다.  결론적으로 유지보수 비용이 더 들 수 밖에 없다는 것이다. 

위에 글을 쓰신 분의 말처럼 재귀로 쓰는 것이 비재귀로 바뀌었을 때보다 메모리나 속도 등의 성능적인 측면에서 떨어진다라는 사실을 인지하고 목적에 따라 재귀로 혹은 비재귀로 선택하여서 사용해야 한다. 

본인이 재귀로 된 것을 비재귀로 바꿀 수 있는 능력이 있다고 해서 모든 프로그래밍에서 비재귀로 바꾸는 것은 이상적인 것을 쫓아가는 것에서 발생하는 현실적이지 못한 판단이 될 수도 있음을 인지하자.
     
푸우 09-03-13 13:34
    
구구절절 옳은 말씀이십니다. 
좋은 의견 감사드리며 제 글에 동의 해주셔서 또한 감사드립니다.