C++ 피보나치 수열 구현하기

피보나치 수열이란

현재 수와 그 앞에 수를 더한값이 다음에 올 수가 되는거다.

맨 처음 숫자 1 이 있다.

앞에 있는 숫자는 0 현재는 1 이니까 다음에 올 수는 1이다.

그다음 현재숫자는 1이고 그전숫자도 1이다. 그러므로 다음에 올 숫자는 2다.

이런식으로 계속 쭉쭉 더해 나가는 것이다.

 

1. for문으로 구현

구현은 생각보다 간단했다.

숫자 한개씩은 계속 가져가야 하니까 작은 숫자를 바꿔주면 되는거다.

#include <iostream>

using namespace std;

void main() {
	int num = 0;
	int num2 = 1;
	int temp;
	for (int i = 0; i < 10; i++) {
		cout << (num > num2 ? num : num2) << " ";
		temp = num + num2;
		if (num > num2) num2 = temp;
		else num = temp;
	}
}

2. 재귀함수로 구현

재귀함수를 사용할땐 조건문을 잘써서 중단 시켜야 한다.

함수는 stack에 메모리가 쌓인다.

그러므로 재귀함수를 잘못 사용하면 stack에 계속 메모리가 쌓여 더이상 공간이 없을때 stack overflow가 뜬다.

우선 시작함 숫자 두개를 입력해주고 몇번 반복할건지 static 키워드를 사용해 카운팅을 한다.

static은 컴파일시 메모리에 할당이 되고 프로그램 종료시 까지 유지된다.

저장되는 공간은 data영역에 저장된다. (data영역엔 static변수와 전역 변수가 저장이 된다.)

출력이 이쁘게 나올수 도록 처음 j값을 같이 찍어줬다...

재귀함수도 for문으로 짰던것 처럼 작은 수를 계속 변경 해줬다.

#include <iostream>

using namespace std;

void Fibonacci(int i, int j, int cnt);

void main() 
{
	Fibonacci(0, 1, 10);
}

void Fibonacci(int i, int j, int cnt) {
	static int loop = 0;
    	if (!loop) cout << j << " ";
	
	cout << i + j << " ";
    
	if (loop++ > 10) return;

	i > j ? j += i : i += j;
	Fibonacci(i, j, cnt);
}

출력이 잘 된것 같다.