문제 번호 10870번 : 피보나치 수 5 - JAVA [자바]

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

문제 설명

 

피보나치 수열은 유명한 수열문제중에 하나입니다. 재귀를 이용해 풀어보도록 하겠습니다.

 

문제 풀이

재귀 문제를 만나면 어떻게 재귀를 만들어야 하는지 막막 할 수 있습니다. 그럴때는 먼저 반복문으로 해당 문제를 풀어보는 것이 중요합니다. 그러면 어떻게 재귀를 사용해야하는지 감이 오기 시작합니다. 반복문으로 다음과 같이 할 수 있습니다.

public static int fibonacci(int n){
    int first = 0;
    int second = 1;
    int result = 0;

    for(int i=1; i<n; i++){
        result = first + second;
        first = second;
        second = result;
    }

    return result;
}

두번째로 더한 값이 첫번째가 되고 두번째 값은 결과 값이 되어 다음 값을 구하는 원리이기 때문에 그대로 조건절로 써줄 수 있습니다.

여기서 재귀를 사용하기 위해서는 first,second가 함수로 들어올때마다 변경 되어야 함이다. int로 선언되어 있으면 계속 같은 값이 반복되어 집니다. 그러므로 매개변수로 선언해줍시다.

public static int fibonacci(int n,int first,int second){
    int result = first + second;

    for(int i=1; i<n; i++){
        result = first + second;
        first = second;
        second = result;
    }

    return result;
}

그럼 이제 for문을 재귀로 변경해주어야 하는데 어렵지 않습니다. for문을 없애고 변하는 값을 매개변수로 넣어주면 됩니다.

public static int fibonacci(int n,int first,int second){
    int result = first + second;

    n--;
    if(n==1){return result;}
    return fibonacci(n,second,result);
}

이런식으로 변경해주면 됩니다. 무한 반복이 되지 않기 위해 if절에 n==1을 넣어주는 것이 중요합니다.

여기서 n이 0혹은 1일때만 신경써 줍시다.

public static int fibonacci(int n,int first,int second){
    int result = first + second;
    if(n==0) return 0;
    else if(n==1) return 1;
    else if(n==2) return result;
    n--;
    return fibonacci(n,second,result);
}

2일때부터 출력함으로 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 result = fibonacci(n,0,1);

        System.out.println(result);
    }

    public static int fibonacci(int n,int first,int second){
        int result = first + second;
        if(n==0) return 0;
        else if(n==1) return 1;
        else if(n==2) return result;
        n--;
        return fibonacci(n,second,result);
    }

}