구현 - 일반적인 재귀용법들

팩토리얼

int recurFacto(int n)

{

if (n < 2) return n;

return n * recurFacto(n - 1);

}

시간 복잡도 분석 : O(n)

n이 1이 될때까지 n번 연산, 데이터의 양 = 연산량

피보나치

int recurFibo(int n)

{

if (n < 2) return n;

return recurFibo(n - 1) + recurFibo(n - 2);

}

 시간 복잡도 분석 : O(2^n)

n이 1이 될때까지 데이터를 하나 연산할 때마다 2개의 연산으로 늘어나고 있다.

자료가 n개 있을 때 연산횟수 k는 n의 개수만큼 2를 곱해야하는 2^n에 가까울 것이다.

바이너리 서치

int recurBsearch(int* arr, int n, int start, int end)

{

if (start > end) return -1;

int middle = (start + end) / 2;

if (arr[middle] == n) 

return middle;

else if (arr[middle] < n)

return recurBsearch(arr, n, middle + 1, end);

else 

return recurBsearch(arr, n, start, middle - 1);

}

시간 복잡도 분석: O(log n)

n이 1이 될 때까지 1/2로 나눠지는 횟수 k가 연산횟수. n * 1/2^k = 1, n = 2^k, k = log 2 n

하노이

void recurHanoi(int n, char from, char by, char to)

{

if (n == 1)

cout << "원반 1을 " << from << "에서" << to <<"로 이동\n";

else

{

recurHanoi(n - 1, from, to, by);

cout << "원반 "<< n << "를 " << from << "에서 " << to << "로 이동.\n";

recurHanoi(n - 1, by, from, to);

cout << "===================================\n";

}

}

 시간 복잡도 분석 : O(2^n)

n개의 블록을 모두 옮기기 위해 (n-1까지의 횟수)*2 - 1를 해야함  즉 *2가 n번이다.

위의 예들을 보며 알 수 있는건 재귀의 본문 안에서 자기자신을 호출할텐데 바이너리서치처럼 범위를 좁히며 탐색하느냐 하노이나 피보나치처럼 늘리면서 연산하느냐에 따라 빅오가 급격히 늘어난다는 것.