[알고리즘] Recursion

순환이란? Recursion

자기 자신을 호출하는 함수

void func(...)
{
	...
    func(...);
    ...
}

 

 

int main() {
	int result = func(4);
}

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

    

무한루프에 빠지지 않으려면 Base case 즉 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 합니다.  단순하게 base case가 무한루프에 빠지지 않는다고 볼 수는 없으며 Recursion을 반복하다 보면 Base case로 반드시 수렴해야 된다는 것입니다. 

 

Recursion의 대표적인 예 : factorial: n!

0! = 1

n! = n * (n-1)!        n>0

int factorial(int n)
{
	if (n == 0)
    	return 1;
    else
    	return n * factorial(n-1);
}

시간복잡도는 o(n) 입니다.

 

 

x^n을 계산하는 것

double power(double x, int n)
{
	if(n==0)
    	return 1;
    else
    	return x*power(x, n-1);
}

 

피보나치 수열

int fibonacci(int n)
{
	if (n < 2)
		return n;
	else
		return fibonacci(n - 1) + fibonacci(n - 2);
}

 

T(n)을 피보나치수열의 n번째 숫자를 계산하기 위한 연산 횟수라고 하면  T(0) = 1, T(1) = 1이다. 또한 T(n-1) > T(n-2) 임으로, 2 이상의 n에 대하여 다음이 성립한다.

T(n) = T(n-1) + T(n-2) + 1 > 2 x T(n-2) > 2^2 x T(n -4).... > 2^n/2 x T(0) = 2^n/2

 

따라서 위 알고리즘의 시간복잡도는 O(2^n)임

 

최대공약수

double gcd(int m, int n)
{
	if (m<n)
	{
		int tmp = m; m = n; m = tmp;
	}
	if (m % n == 0)
		return n;
	else
		return gcd(n, m % n);
}

int gcd(int p, int q)
{
	if (q == 0)
		return p;
	else
		return gcd(q, p % q);
}