C 언어 재귀구조의 피보나치 수열 만드는 방법

피보나치 수를 처음 연구한 사람은 레오나르도 피보나치로 토끼 수의 증가에 대해 이야기 하면서 언급했던 내용입니다. 첫 달에는 새로운 토끼 한쌍에서 시작합니다. 두 달 이상 되는 토끼만 번식이 가능하며 매달 한쌍씩만 낳습니다. 이렇게 토끼의 쌍이 늘어나는 수를 피보나치 수라고 합니다. 결과는 1, 1, 2, 3, 4, 8, 13, 21 … 증가하게 됩니다. 이것을 C 언어로 구해 보겠습니다. 

 

 

 

◎ 재귀 함수를 이용해서 구하기

 

 

▼ 피보나치의 수식은 다음과 같습니다. 이것을 C 소스로 구현할 것입니다. 먼저 재귀 함수를 이용한 방법입니다.

 

 

▼ 피보나치 수열의 기본 규칙은 처음 두 항은 1이고 세 번째 항부터 이전 두 항의 합이 됩니다. 1, 1, 2 다음부터 1+2 가 다음 항이 되는 것이죠. 그 다음은 2+3=5가 되겠죠. 이것을 기반으로 로직을 짜시면 됩니다. 이전에 계산된 값이 필요하기 때문에 fibo 함수 내에서 n =0 이 될 때까지 fibo 함수를 다시 호출하는 것입니다. 

#include <stdio.h>
#include <stdlib.h>

int fibo(int n) ;

int main(void){
	int n;
	int i;

	printf("\n피보나치 수 입력 : \n" );
	scanf("%d" , &n) ;

	for(i = 0 ; i < n ; i++ ){
		printf("%d " , fibo(i));
	}

	printf("\n\n");
		
	system("pause");
	return 0;

}

int fibo(int n){
	if(n == 0) return 0;
	else 
		if(n == 1) return 1;
	else 
		return fibo(n-1) + fibo(n-2);
}

 

※ 아래는 참고하면 좋을 만한 글들의 링크를 모아둔 것입니다. ※ ▶ C 언어 printf 함수 이용해서 문자열을 출력하는 방법 ▶ C 언어 무료 컴파일 도구 Dev C++ 새 프로젝트 만들어서 실행하기 ▶ C 언어 무료 컴파일 도구 Dev C++ 디버깅 하는 방법 ▶ C 언어 Visual Studio 실행 후 콘솔 창 유지하기 위한 방법 ▶ C 언어 재귀구조의 피보나치 수열 만드는 방법

 

 

◎ 반복문으로 만들기

 

 

▼ 이번에는 별도의 함수는 만들지 않고 for 문 만으로 구현한 소스입니다. 먼저 변수를 3개 만듭니다. 0, 0, 1 든 3가지 변수를 만들고 한 단계 전에 값과 두 단계 전에 값을 더해서 만드는 것입니다. head 가 두 단계 전 값이며 rear 이 한 단계 전 값이 됩니다. 두 개의 변수에 저장된 값을 더해서 수열을 만들게 됩니다. 

#include <stdio.h>
#include <stdlib.h>

int main(void){

	int i ;
	int n;
	int head = 0;
	int mid = 0;
	int rear = 1;
	
	printf("\n 피보나치 수 입력 : ");
	scanf("%d" , &n) ;
	
	for(i = 0 ; i < n ; i++){
		printf("%d " , head) ;
		mid = head+rear;
		head = rear;
		rear = mid;
	}

	printf("\n\n");
	system("pause");
	return 0 ;
}

 

※ 아래는 참고하면 좋을 만한 글들의 링크를 모아둔 것입니다. ※ ▶ C 언어 printf 함수 이용해서 문자열을 출력하는 방법 ▶ C 언어 무료 컴파일 도구 Dev C++ 새 프로젝트 만들어서 실행하기 ▶ C 언어 무료 컴파일 도구 Dev C++ 디버깅 하는 방법 ▶ C 언어 Visual Studio 실행 후 콘솔 창 유지하기 위한 방법 ▶ C 언어 재귀구조의 피보나치 수열 만드는 방법