Recursion vs. Iteration : Round 3

부제 : 말이나 못하면 밉지나 않지. (?)



자, 이번에는
"Round 1"에서의 피보나치 수열을 나름 "개량된" 재귀함수로 구현해보도록 하겠습니다

... // #include 외 unsigned improvedRecursion( unsigned, unsigned * ); void main() { ... // 선언부 unsigned count; unsigned *fibonacciSequence; cout << "number? : "; cin >> count; fibonacciSequence = ( unsigned * )calloc( 1+count, sizeof( unsigned ) ); ... // 시간 측정 시작 improvedRecursion( count, fibonacciSequence ); ... // 시간 측정 끝 free( fibonacciSequence ); } unsigned improvedRecursion( unsigned n, unsigned *ary ) { if( ary[n] != 0 ) return ary[n]; else if( n <= 2 ) { ary[n] = 1; return ary[n]; } else { ary[n] = improvedRecursion( n-1, ary ) + improvedRecursion( n-2, ary ); return ary[n]; } }
(동적 할당을 new가 아닌 calloc으로 하는 것에는 그닥 신경쓰지 말고 -_-;)

다른 점이 눈에 보이십니까?


Fn에서의 n 외에 배열을(엄밀히 말하면 포인터지만) input으로 하나 더 받고 있는데

이놈이 하는 역할이 뭔고 하니

배열에서의 n번째 위치에 저장된 값(Fn)이 0이면 Fn-1과 Fn-2의 합을 Fn에 저장한 뒤 리턴하고,
0이 아니면 즉시 그 값을 리턴하도록 Fn을 기록해두는 역할을 하고 있습니다

n = 5
impR(5) 호출
fSeq[5] 검사, fSeq[5]의 값이 0인가?
True ⇒ fSeq[5] = impR(4) + impR(3) 시행

　impR(4) 호출
　fSeq[4] 검사, fSeq[4]의 값이 0인가?
　True ⇒ fSeq[4] = impR(3) + impR(2) 시행

　　impR(3) 호출
　　fSeq[3] 검사, fSeq[3]의 값이 0인가?
　　True ⇒ fSeq[3] = impR(2) + impR(1) 시행

　　　impR(2) 호출
　　　fSeq[2] 검사, fSeq[2]의 값이 0인가?
　　　True ⇒ n ≤ 2 이므로 fSeq[2] = 1 시행 후 fSeq[2] 리턴

　　　impR(1) 호출
　　　fSeq[1] 검사, fSeq[1]의 값이 0인가?
　　　True ⇒ n ≤ 2 이므로 fSeq[1] = 1 시행 후 fSeq[1] 리턴

　　시행결과 : fSeq[3] = 2

　　impR(2) 호출
　　fSeq[2] 검사, fSeq[2]의 값이 0인가?
　　False ⇒ fSeq[2] 리턴

　시행결과 : fSeq[4] = 3

　impR(3) 호출
　fSeq[3] 검사, fSeq[3]의 값이 0인가?
　False ⇒ fSeq[3] 리턴

시행결과 : fSeq[5] = 5

fSeq[5] 리턴

설명은 이정도로 하고, 실행시간을 재보도록 할까요?

예전의 재귀보다 훨씬 빠르죠?

개인적으로는 거의 반복과 비슷한 수준에 이르렀다고 생각합니다

그러나, 위에서도 볼 수 있듯이

input이 40000을 찍는 순간, 우리의 컴퓨터는 함수를 호출할 메모리가 부족하여 재귀를 멈춰버리고 맙니다
(실제로 40000까지 안전한건 아니고, 저희 집의 경우 12000정도만 찍어도 재귀가 멈춰버리는 듯 하더군요)


그리하여, 속도는 비슷한 듯 하지만 메모리상의 문제에서 재귀가 패배하게 됩니다



여태까지 언급했던 것들 외에 재귀가 반복보다 빠른 케이스를 지난 주에 한가지 언급해드렸습니다

바로 멱(거듭제곱)을 구하는 것입니다

이건 따로 시간을 잰다거나 하지 않고 간단히 소스만 보고 넘어가도록 하죠

int power_R( int x, int y ) { if( y == 1 ) return x; else { if( y%2 ) { return x*power_R( x*x, ( y-1 )/2 ); } else { return power_R( x*x, y/2 ); } } }

int power_I( int x, int y ) { if( y == 1 ) return x; else { int i; int result = x; for( i = 2; i <= y; i++ ) { result *= x; } return result; } }

R은 재귀, I는 반복입니다

반복의 경우 시간복잡도가 O(n)이지만 재귀의 경우는 시간복잡도가 O(log_2 n)정도밖에 되지 않습니다

그래서 이 경우에는 재귀가 반복보다 "훨씬" 빠르겠습니다





피보나치 수열에 대해 얘기를 하다가 "재귀vs.반복"으로 빠져버렸습니다만

굳이 결론을 내리자면 "상황에 따라 더 적절한 것을 사용하는" 것이 괜찮을 거라 생각합니다

다음번에는 다른 주제를 얘기해보도록 하겠습니다~



여담이지만,
피보나치수열의 값을 구하는 데 있어서 수학함수를 사용하면 반복보다 훨씬 더 빠르게 되는 식이 있습니다 :D

(포스팅 소요시간 : 약 70분)