코드업(Codeup) 1916 : (재귀함수) 피보나치 수열 (Large)

import java.util.Scanner;
import java.util.List;
import java.util.Vector;

public class Main {	
    static int cnt = 2;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int rs = 0;

        // 188
        if(n < 3) rs = 1;
        else rs = Start(1, 1, n);

        System.out.println(rs);
    }

    static int Start(int num1, int num2, int n) {
        int num3 = (num1 + num2) % 10009;
        cnt++;

        if(cnt < n) num3 = Start(num2, num3, n);

        return num3;
    }
}