나 사랑하는 것과 영원히 함께 흘러가

나 잃어버린 것보다 이뤄갈 날을 위해 흘러가

C 자세히보기

C Drill

C 재귀(Recursion) 예제 #2 - 피보나치 수열(Fibonacci numbers)

새미 소사 2025. 3. 16. 17:20
반응형

피보나치 수열(English): https://oeis.org/A000045

 

A000045 - OEIS

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334

oeis.org

재귀 함수를 이용하여 양의 정수인 n을 scanf로 저장해(#define _CRT_SECURE_NO_WARNINGS 사용) n번째 피보나치 수열( F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1. )을 출력하라.

 

 

 

예시:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int fibonacci(int);

int main()
{
	int num=0;//n번째 피보나치 수열
	printf("알고 싶은 n번째 피보나치 수열(양의 정수): ");
	scanf("%d", &num);
	if (num <= 0) {
		printf("0과 unsigned integer는 허용되지 않습니다.");
		return - 1;
	}
	printf("%d", fibonacci(num));
}

int fibonacci(int n)
{
	if (n == 0 || n == 1) { //Base case
		return n;
	}
	return fibonacci(n - 1) + fibonacci(n - 2); //Recursive case
}

점화식이 제시되어 있어 쉽게 문제를 풀 수 있었습니다. n = 5일 때 재귀 호출이 이루어지는 과정을 살펴보면 다음과 같습니다.

<<재귀 호출 과정(Stack frame이 쌓이는 과정)>> //Stack의 처리순서는 LIFO(후입선출)이다.
① fibonacci(5) = fibonacci(4) + fibonacci(3)  → (fibonacci(5)를 계산하려면 fibonacci(4), fibonacci(3) 호출)  
② fibonacci(4) = fibonacci(3) + fibonacci(2)  → (fibonacci(4)를 계산하려면 fibonacci(3), fibonacci(2) 호출)
③ fibonacci(3) = fibonacci(2) + fibonacci(1)  → (fibonacci(3)를 계산하려면 fibonacci(2), fibonacci(1) 호출)
④ fibonacci(2) = fibonacci(1) + fibonacci(0)  → (fibonacci(2)를 계산하려면 fibonacci(1), fibonacci(0) 호출)
⑤ fibonacci(1) = 1  (Base case)
⑥ fibonacci(0) = 0  (Base case)

<<Base case에 도달한 후 반환값 계산>>
① fibonacci(2) = 1 + 0 = 1
② fibonacci(3) = 1 + 1 = 2
③ fibonacci(4) = 2 + 1 = 3
④ fibonacci(5) = 3 + 2 = 5

재귀 호출은 Stack 프레임을 사용하여 진행되며 가장 마지막 호출된 함수부터 차례로 종료되면서 값이 계산됩니다.

 

지적 환영합니다. 댓글로 고견 부탁드립니다.

유익했다면 포스트 좌하단의 ♡공감 꾹 눌러주시면 글쓴이에게 힘이 됩니다!

반응형