<피보나치 수열>: #순환 버전 #반복 버전

# 피보나치 수열 문제

---

 Fibonacci 수열은 다음과 같이 정의된다.

$f_0 = 0, f_1 = 1 그리고 f_i = f_{i - 1} + f_{i - 2}(i > 1 일 때)$

$f_i$를 계산하는 C함수로 순환 함수와 반복 함수를 모두 작성하라.

# 구현 // 반복버전에서 반복계수가 2부터 시작해서 n까지 간다는 것만 주의하면 된다. 반복계수가 2인 까닭은 2개의 초기값을 설정해줬기 때문에 0과 1을 지나쳐 2부터 시작되는 것이다.

---

/*************************************************
 **Fibonacci iterative & recursive ver
*************************************************/

#include <stdio.h>

int recur_fibo(int n);
int iter_fibo(int n);

void main()
{
	int n;
	while (1)
	{
		printf("테스트를 원하는 양의 정수를 입력해주세요. 음수를 입력하면 프로그램을 종료합니다.\n");

		scanf("%d", &n);

		if (n < 0)
			break;

		printf("순환 버전 피보나치 결과: %d\n", recur_fibo(n));
		printf("반복 버전 피보나치 결과: %d\n", iter_fibo(n));
	}
}

int recur_fibo(int n)
{
	if (n <= 1)
		return n;

	return recur_fibo(n - 1) + recur_fibo(n - 2);
}

int iter_fibo(int n)
{
	int i;
	int f0, f1, fi;

	// 초기값 설정
	f0 = 0;
	f1 = 1;

	// 예외처리
	if (n == 0) return 0;
	else if (n == 1) return 1;

	else
	{
		for (i = 2; i <= n; i++)
		{
			fi = f0 + f1;
			f0 = f1;
			f1 = fi;
		}
	}
	return fi;
}

/*************************************************
 ** End Line
*************************************************/