Baekjoon | Q.10870 - 피보나치 수 5

10870번: 피보나치 수 5

 재귀함수를 이용하여 n번째 피보나치 수를 구하는 문제이다. 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int fn_2 = 0;
        int fn_1 = 1;

        int fn = Fibonacci(fn_2, fn_1, n);

        System.out.println(fn);

        sc.close();
    }

    static int Fibonacci(int fn_2, int fn_1, int n) {

        int fn = fn_1 + fn_2;

        if(n == 0) return 0;
        else if(n == 1) return 1;
        else if(n > 2) {
            fn_2 = fn_1;
            fn_1 = fn;
            n--;
            return Fibonacci(fn_2, fn_1, n);
        }

        return fn;
    }
}

 

 내가 풀어본 코드이다. 0과 1을 초기값으로 넣어주고 횟수(n)을 값을 더할 때마다 감소시키는 방식이다.

 

 그런데 다시 함수를 부를 때 return을 붙이지 않으면 왜 제대로된 결과값이 나오지 않는지 모르겠다.. n=2가 되면 바로 fn이 return되도록 하였는데 자꾸만 다시 함수를 부른다....ㅠㅠ

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int fn = Fibonacci(n);

        System.out.println(fn);

        sc.close();
    }

    static int Fibonacci(int n) {
        if(n == 0) return 0;
        else if(n == 1) return 1;

        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

 

 인터넷 서치를 해본 결과 더 간단한 코드가 있었다 ..ㅎ n번째를 구하기 위해서 n-1, n-2, ..., 0번째 피보나치 수까지 거슬러 올라가는 방법으로 해석된다.