백준 10870번 자바 피보나치 수 5 [재귀]

n을 입력한다.

피보나치 수열에서 n번째 수는 몇 인지 출력하는 프로그램이다.

Fn = Fn-1 + Fn-2 이렇게 공식도 친절히 나와있다.

 

즉 5번째 수는 4번째 + 3번째 라는 의미이다.

 

그럼 4번째 수와 3번째 수를 알아야 한다.

4번째는 3번째 +2번째 이며 2번째는 0번째 + 1번째이다.

0번째는 0이고 1번째는 1이다. 

 

이렇게 n을 입력하고 -1, -2 쭉쭉해서 0번째와 1번째에서 0과 1을 리턴하면서 더하고 더하고 더해서 최종 리턴하면

n번째 피보나치 수를 구할 수 있다.

import java.util.Scanner;
 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
       
        int n = sc.nextInt();
        
        System.out.println(fivo(n));
        
    }
    
    static int fivo(int n) {
        
        if(n == 0)
            return n;
        else if(n == 1)
            return 1;
        
        return fivo(n-1) + fivo(n-2);
    } 
}