<알고리즘/C++> 재귀함수/피보나치 수열

 

간단한 예제로는 피보나치 수열에 대한 설명이 있습니다.

위의 수식은 1부터 시작하는 피보나치 수열의 식이다.

위의 수식은 0부터 시작하는 피보나치 수열의 식이다.

 

시작이 1부터면 

결과는 

 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946 이런식으로 나올겁니다.

 

그렇다면 코드로 한번 확인해보겠습니다.

메인입니다. 결과값을 불러주기위해서 Fibonacci(피보나치) 함수를 만들어줬습니다.

int main() {
	int num;
	cin >> num;

	cout << Fibonacci(num) << endl;


	system("pause");
	return 0;
}

여기서  재귀함수(recursion)를 사용할겁니다. 

Fibonacci(피보나치) 함수를 확인해보겠습니다.

1번과 2번은 값이 1이기 때문에 무조건 1이나 2가 들어오면 1로 리턴해줍니다. 

int Fibonacci(int num) {
	if (num == 1)
		return 1;

	if (num == 2)
		return 1;

	
	return Fibonacci(num-1) + Fibonacci(num-2);

}

그리고 Fibonacci(피보나치) 자기 자신을 다시 불러옵니다 이를 재귀함수라고 합니다 마치 반복문처럼 움직입니다. 

num이 8이라는 가정하에 정답은 21이라는 값이 나와야합니다.

 

한번 하나씩 따라가보도록 하겠습니다.

그림으로 나타내면 

 

Fibonacci(2) , Fibonacci(1) 각각 1이 될겁니다. 그림의 부분에서 이부분부터 하나씩 숫자를 더해서 올라오면 

21이라는 숫자가 될겁니다. 

시간 복잡도 O(2^n)