[Java] 백준알고리즘 #10870 피보나치 수 5

백준알고리즘 #10870 피보나치 수 5

 

재귀함수를 이용해서 피보나치 수를 구하는 방법.

 

피보나치 수는

0번째 수가 0,

1번째 수가 1,

2번째 수부터는 0번째 수 + 1번째 수

...

 

과정을 거치므로 재귀함수를 이용하기에 적합하다.

 

재귀함수를 이용하여 팩토리얼을 구했을 때 처럼 fibo함수를 이용한다면

fibo(n) = fibo(n-1) + fibo(n-2) 가 될 것이다.

위 과정을 반복하다 보면, fibo(0), fibo(-1) ... 처럼 무한히 끝나지 않을 수 있으니, 종료 조건을 명시해주어야 한다.

fibo(n-1) + fibo(n-2)가 각각 fibo(1)과 fibo(0) 일 때, 이 루프가 끝나게 되므로

fibo(1)은 1, fibo(0)은 0으로 명시해준다. (종료조건 충족)

 

전체 코드는 다음과 같다.

 

// 해설참조 : sehyeok.tistory.com 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        System.out.println(fibo(n)); // 출력
        br.close();
    }
    public static int fibo(int n) {
        if (n == 0) {		// 0번째 수 (재귀함수 종료조건 충족)
            return 0;
        }
        if (n == 1) {		// 1번째 수 (재귀함수 종료조건 충족)
            return 1;
        }
        n = fibo(n - 1) + fibo(n - 2);	// 자기자신 호출(재귀)
        return n;
    }

}