[코드업]1916 : (재귀함수) 피보나치 수열 (Large) | C

#include <stdio.h>
using namespace std;
int n;
int f(int a, int b){
    if(n<=0)
        return b;
    else{
        n--;
        return f(b,(a+b)%10009);
    }
}
int main(){
    scanf("%d", &n);
    n-=2;
    printf("%d", f(1,1));
    return 0;
}

사용자로부터 n을 입력받고, 이에 해당하는 피보나치 수를 출력하는 문제이다.
단 n은 200 이하이며, n이 커질 수 있으므로, 10,009를 나눈 나머지 값을 출력한다.


f() 설명:
이름은 f인 함수이고,
반환값의 자료형은 int이다.
매개변수는 피보나치 수열의 시작인 1, 1을 int a, int b로 받고, 피보나치 수열은 연속된 두 수를 더하면 다음 수이므로,
다음부터는 b, a+b를 매개변수로 받는다.


만약 사용자가 첫 번째 혹은 두 번째 피보나치 수를 입력하면 계산할 필요가 없다. 
피보나치 수열에서 첫 번째와 두 번째는 1이라고 약속했기 때문이다.
따라서 사용자가 물어본 n번째 피보나치 수를 구하려면 n-2번 계산하면 된다.

그렇기 때문에 n을 입력받으면 n-=2;를 실행하는 것이고, n이 1이나 2라면 음수일 것이므로
즉시 b를 반환한다. 그뿐만 아니라 n을 1씩 감소시키면서 몇 번 계산할지를 셀 건데, 이때 0이 되면 다 센 것이므로, 
0일 때도 b를 반환하는 것이다.

 

하지만 위 경우가 아니라면, 아직 계산을 더 해야 한다는 것이다.
따라서 인자로 b와 (a+b)%10009를 가진 재귀함수를 호출하고,

그 전에 남은 계산 횟수를 세기 위해서 n을 1 만큼 감소시킨다.



main() 설명:
사용자로부터 n을 입력받는다.
n-=2; 후에 printf("%d", f(1,1)); 를 실행하여 n번째 피보나치 수를 출력한다.

이때, f()는 매개변수로 int 형 변수 2개를 갖고 반환값이 있다는 걸 알 수 있으며

서식문자 %d이기 때문에 자료형이 int라는 것을 알 수 있다.