[C]백준 10.재귀: 10870

백준 10870

내코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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

int main()
{
	int n;
	scanf("%d", &n);
	printf("%d", fibonacci(n));
	return 0;
}

피보나치 수식인 F(n) = F(n-1)+F(n-2) (n>=2)를 이용해 식을 세웠다. F(0)은 0이고, F(1)은 1이기에 n이 0일땐 0을 리턴하고, n이 1일땐 1을 리턴하며, 그외엔 fibonacci(n-1) + fibonacci(n-2)를 리턴하는 함수를 만들었다.

 

예를 들어 fibonacci(4)를 호출한다면 fibonacci(3)+fibonacci(2)를 리턴하기 전 fibonacci(3)과 fibonacci(2)를 호출할 것이다. fibonacci(3)을 호출한다면 fibonacci(2)+fibonacci(1)을 리턴하기 전 fibonacci(2)와 fibonacci(1)을 호출할 것이다. fibonacci(2)를 호출한다면 fibonacci(1)+fibonacci(0)을 리턴하기 전 fibonacci(1)과 fibonacci(0)을 호출할 것이다. fibonacci(1)은 1을 , fibonacci(0)은 0을 리턴하기에 fibonacci(2)는 1+0=1을 리턴할 것이다. fibonacci(3)은 1+1=2를 리턴할 것이고, fibonacci(4)는 2+1=3을 리턴할 것이다.