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

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

A000045 - OEIS

재귀 함수를 이용하여 양의 정수인 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 프레임을 사용하여 진행되며 가장 마지막 호출된 함수부터 차례로 종료되면서 값이 계산됩니다.

 

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

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