[자료구조] 순환함수

Factorial

n이 1씩 감소하는 방향으로 진행
결국은 n이 0에 도달, 그 때 단순해는 1

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

Fibonacci

n이 1과 2씩 감소하는 방향으로 진행
결국은 n이 0 또는 1에 도달, 그 때 단순해 Fib(0)=0, Fin(1)=1

int Fib(int n) {
	//2차 피보나치
	if (n <= 1)
		return n;
	else
		return Fib(n - 1) + Fib(n - 2);
	return 0;
	//3차 피보나치
	/*if (n <= 2)
		return n / 2;
	else
		return Fib(n - 1) + Fib(n - 2) + Fib(n - 3);
	return 0;*/
}

Combination

n이 또는/그리고 r이 1씩 감소

• n이 작아져 n=r에 도달, 그 때 단순해는 C(n,n)=1
• n과 r이 작아져 r=0에 도달, 그 때 단순해는 C(n,0)=1

int Combi(int n, int r){
	if (n == r || r == 0)
		return 1;
	return Combi(n - 1, r) + Combi(n - 1, r - 1);  //n≥r 일 때
}

Hanoi Tower

한번에 1개의 층만 옮길 수 있다.
작은 층 위에 큰 층을 올릴 수 없다.
탑을 목적지로 이동하는데, 한 곳만 더 임시로 이용할 수 있다

void hanoi(int n, int nFrom, int nTo) {
	if (n == 1)
		printf("%d ==> %d\n", nFrom, nTo);
	else {
		int nTemp = 6 - nFrom - nTo; //중간에 잠깐 놓는 곳
		hanoi(n - 1, nFrom, nTemp);  // 위의 n-1개 층을 우선 나머지 위치로 피신해두고
		hanoi(1, nFrom, nTo);  // 맨 아래 층을 목적지로 욺기고
		hanoi(n - 1, nTemp, nTo);  // 피신해 둔 위의 n-1개의 층을 목적지로 옮긴다.
	}
}

Euclid

GCD(A, B) = GCD(B, A%B)
A에서 B를 나눈 나머지로 바뀌면서 작아지는 방향으로 진행
결국은 A는 B로 나누어짐, 그 때 단순해는 B

int Euclid(int nBig, int nSmall)
{	// GCD(Greatest Common Divisor)를 계산한다
	int nRem = nBig % nSmall;
	if (nRem == 0)
		return nSmall;
	return Euclid(nSmall, nRem);
}

Skip Erase

일반규칙: f(n)=2f(n/2)-1(짝수), 2f(n/2)+1(홀수) //n이 절반으로 감소
중단조건 및 단순해: f(1)=1

int SkipEraser2(int n) // 순환 함수로 작성
{
	if (n == 1)
		return 1;
	return 2 * SkipEraser2(n / 2) + n % 2 * 2 - 1;
}