재귀(Recursion) 응용 문제

스터디에서 재귀 파트를 나갈 때, 친구가 과제였던 것을 가져왔다. 이 간단한 것으로.. 하루 종일 고민했다..

 

<문제>

<출력 예>

 

재귀 문제이므로, 재귀로 푼다!

 

1) n이 0또는 1일 때, 1을 리턴한다.

2) Hn을 쭉 나열해보면, 곱할 때의 두 항의 합이 n-1이 되도록 H0부터 Hn-1까지 더해 주는 것을 확인할 수 있다.

for (i = 0; i < n; i++)
			sum += H(i) * H(n - i - 1);

   따라서 H()의 인자 값의 합이 항상 n-1이 되도록 반복문을 설정해 주고, sum에 계속 더해준다.

 

 

<완성 코드>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int H(int n) {

	int i, sum = 0;

	if (n == 0 || n == 1) return 1;
	else {
		for (i = 0; i < n; i++)
			sum += H(i) * H(n - i - 1);
		return sum;
	}
}

int main(void) {
	int n, i;

	printf("구하려는 함수 H의 값: ");
	scanf("%d", &n);

	//printf("%d", H(n));
	for (i = 0; i <= n; i++)
		printf("i = %d일 때 %d\n", i, H(i));
}

p.s) 백준에서의 문제였다면, 반복문을 재귀와 사용하게 되면 시간 초과가 날 것 같다.