#include <stdio.h>
#include<Windows.h>
#pragma warning (disable : 4996)

int G_func(int);	// 함수 원형 정의

void main()
{
	int i;
	// F(N+2)=2F(N)+F(N+1)과 같은 점화 관계에 대해 구하려고 하는 항을 입력받음
	printf("구하려고 하는 항을 입력하라. : ");
	scanf("%d", &i);
	// 재귀함수인 G_func를 통해 입력된 i에 대해 F(i)를 계산해서 결과 출력
	printf("%d번째 항의 값 F(%d) = %d\n", i, i - 1, G_func(i - 1));
	system("PAUSE");
}

// 재귀함수로 정의된 점화 관계
int G_func(int n)
{
	// 항이 0이거나 0보다 클 때 계속 진행
	if (n >= 0)
	{
		// 항이 1 아니면 0일 때 1을 반환
		if (n <= 1)
			return 1;
		// 점화 관계 2F(N)+F(N+1)을 반환
		return 2 * G_func(n - 2) + G_func(n - 1);
	}
}