1196: [기초-재귀설계] 재귀로 n번째 피보나치 수 출력하기(설명)

*주의사항 : 이 문제는 재귀 설계 문제로서 반복문을 사용한 코드는 채점이 되지 않습니다.
------

한 정수 n을 입력받아 n번째 피보나치 수를 출력하시오.
(단, 반복문은 사용할 수 없다.)


참고
프로그래밍언어에서의 재귀 함수는?
- 함수를 정의할 때, 자기 자신을 호출해 사용하는 형태로 정의된 함수라고 할 수 있으며
- 3가지 종류와 2가지 방향으로 크게 구분지어 생각해 볼 수 있다.
- 3가지 종류 : 단순/다중/복합
- 2가지 방향 : 하향식/상향식

다중 재귀는?
함수를 정의하는 도중에 자기 자신을 2번 이상 호출하는 방법이다.
하향식 방법은?
큰 문제의 답을 얻기 위해서 이전에 얻어낸 같은 형태의 보다 작은 문제의 해결 결과를 이용하는 방법이다.


n번째 피보나치 수를 출력하는 문제는
다음과 같은 다중 재귀 하향식 방법으로 설계하여 해결할 수 있다.

n번째 피보나치 수를 계산하는 문제의 하향식 재귀 설계 방법(예시)
- 하향식
n번째 피보나치 수를 계산하는 문제는 (n-2)번째 피보나치 수와 (n-1)번째 피보나치 수를 구한 상태에서 그 합을 구하는 문제로 바꿀 수 있다.
...
2번째 피보나치 수는 1이다.
1번째 피보나치 수는 1이다.


재귀 함수를 정확하게 설계하기 위해서는

1. 가장 먼저! : 자신이 만들고자하는 “재귀 함수의 의미”를 명확하게 생각한 후,

2. 그 다음에 : “큰 문제와 작은 문제 사이의 관계(하향식)”나 “현재 상태에서 다음 상태로의 변화관계(상향식)”와 같은
관계를 분석해 작성하고,

3. 마지막에 : “가장 작은 문제 상태”나 “가장 큰 문제 상태”를 생각해
재귀 호출의 중단 조건과 그 상태에서의 리턴 값을 작성해 넣으면 된다.


n번째 피보나치 수를 계산하는 문제에 대해서 하향식 재귀 설계 방법을 적용해 본다면,

1. f(n)을 n번째 피보나치 수라고 생각(정의)한다.

그러면,
f(k)는 k번째 피보나치 수이고,
k번째 피보나치 수를 구하는 문제는,
(k-2)번째 피보나치 수와 (k-1)번째 피보나치 수를 이미 구한 상태에서 그 합을 출력하는 문제로 바꾸고 일반화 시킬 수 있다.

f(k) = f(k-2)+f(k-1)

함수 호출 위치에 리턴하는 값이 정수 값이므로, 정수형(int, long long int) 함수로 설계해야 한다.


2. 1.에서 만든 명확한 정의와 큰 문제를 보다 작은 문제로 바꾸는 관계를 이용해 함수로 작성(설계)한다.

long long f(int k) //k번째 피보나치 수를 구하는 문제는
{
  return f(k-2)+f(k-1); //(k-2)번째 피보나치수와 (k-1)번째 피보나치수를 합한 값이다.
}

이렇게 큰 문제를 해결하기 위해, 보다 작은 문제를 해결한 결과를 이용하도록 만 작성하면
무한 재귀 호출 상태에서 빠져나오지 못하기 때문에
재귀 호출을 중단시키기 위한 중단 조건과 처리해야할 작업을 추가로 작성해 넣어야 한다.


3. 2.에서 만든 함수에 재귀 호출 중단 조건과 리턴해야 할 값을 추가한다.

가장 처음 시작하는 첫 번째 피보나치 수를 1, 두 번째 피보나치 수를 2라고 하면,
다음과 같은 재귀 호출 중단 조건을 추가할 수 있다.
(함수 호출 중단 시에는 이전 위치에 돌려다 놓는 값을 return 값; 으로 작성해야 한다.)


long long f(int k) //k번째 피보나치 수를 구하는 문제는
{
  if(k <= 2) return 1; //첫 번째와 두 번째 피보나치 수는 1이다.(부등식이 안정적)
  return f(k-2)+f(k-1);
}
와 같이 어떤 상태까지만 재귀적으로 호출되는 재귀 함수를 완성시킬 수 있다.


위와 같은 생각과 함수 설계 과정을 통해,
f(n)을 호출하여 n번째 피보나치 수를 출력하는 예시코드는 다음과 같이 작성할 수 있다.

#include <stdio.h>

int n;

long long int f(int k)
{
  if(k <= 2) return 1;
  return f(k-2)+f(k-1);
}

int main()
{
  scanf("%d", &n);
  printf("%lld\n", f(n));
}

int 형 정수(n) 1개가 입력된다.
(1 <= n <= 30)

n번째 피보나치 수를 출력한다.

6

8