[C언어 알고리즘] Recursion 재귀함수

< 순환 Recursion >

   함수 안에서 함수 자기 자신을 호출하는 것

   탈출 부분과 지속 부분으로 나누어져 있음

 

  장점

•  일반적으로 코드가 짧다.
•  이해가 쉽다.

  단점

• 메모리를 많이 차지한다. (자기 자신이 끝나지 않은 상태에서 계속해서 호출하게 되면 이전상태를 기억해야 한다. 이때문에 메모리를 놓지 않고 잡고 있게 되어 메모리를 많이 차지하게 된다.)
• 시간이 많이 걸린다. (함수를 계속해서 호출하면서 시간이 걸리게 된다.)

 

---

 

ex_1) 거듭제곱 계산하기 : power(x,n)

    non-recursive --> for문이용

    recursive

       탈출 조건 => if n==0 return

       지속 조건 => return x*power(x,n-1)

 

    p(x,n)

      1. 탈출 if n==0 > return 1

      2. 지속 if n %2 ==0  return p(x^2, n/2)

                   n %2 ==1  return x*p(x^2, (n-1)/2)

 

  반씩 줄여나가므로, for문 도는것 보다 실행시간이 짧음

 

 

 

#include <stdio.h>

//v의 a승
//0^0은 제외
int calc_power_by_recursion(int v, int a)
{
	//탈출조건
	if (a == 0) return 1;

	if (a % 2 == 0)
	{
		return calc_power_by_recursion(v * v, a / 2);

	}
	else
	{
		return v * calc_power_by_recursion(v * v, (a - 1) / 2);

	}
}

int main(void)
{
	//2^4
	printf("2 power 4 ---> %d\n",calc_power_by_recursion(2,4)); //16
	//3^5
	printf("3 power 5 ---> %d\n", calc_power_by_recursion(3, 5)); //243
	//100^0
	printf("100 power 0 ---> %d\n", calc_power_by_recursion(100, 0));

	return 0;
}

 

 

ex_2) 피보나치 수열

   1,1,2,3,5,8,13, ....

   f(n) = ? ... n번째 피보나치 수열 =?

   f(0) =1 , f(1)=1

     1. 탈출조건 if n==0 || n==1 return 1

     2. 지속조건 return f(n-1)+f(n-2) 

#include <stdio.h>

/* Fibonacci 수열 구하기 by recursion

  Fibo(n) : n번째 숫자를 반환
  1,1,2,3,5,8,13,21,34,55,89,144...
*/


int fibo(int _n)
{
	//exit condition
	if ((_n == 1) || (_n == 2))
	{
		return 1;
	}

	return fibo(_n - 1) + fibo(_n - 2);

}


int main(void)
{
	printf("Fibo(6) --> %d\n", fibo(9)); //34
	printf("Fibo(15) --> %d\n", fibo(12)); //144
}

 

 

 

ex_3) 하노이탑

(옮겨야할 원판갯수, 출발지 tmp를 이용, 최종 목적지)

1. 탈출 if(n==1) f->t return

2. 지속 : 큰거 from->to

 

 

#include <stdio.h>

// n개의 접시를 from에서 to까지 옮긴다.
// 이 때, tmp를 임시로 사용한다.
void hanoi(int n, int from, int tmp, int to)
{
	//exit condition
	if (n == 1)
	{
		printf("move dish from %d to %d\n", from, to); //옮기는 과정에서 출력
		return;
	}

	//recursive condition
	//접시가 2개 이상일 때,

	//1. n-1개를 from-->tmp로 옮겨 놓는다. 임시(to)
	hanoi(n - 1, from, to, tmp);
	//2. 1개를 from-->to로 옮긴다. (임시 tmp)
	hanoi(1, from, tmp, to);
	//3. n-1개를 tmp-->to로 옮긴다. (임시from)
	hanoi(n - 1, tmp, from, to);

}

int main(void)
{
	//3개의 접시를 1번에서 3번으로 옮겨라 (임시로 2번 사용가능)
	hanoi(4, 1, 2, 3);
	return 0;
}