[백준,BOJ 10870] 피보나치 수 5(JAVA 구현)

-해법

import java.util.Scanner;

public class Main{
	
	static int fibonacci(int n) { // 피보나치 메소드
		if(n == 0) return 0; // 0이면 0을 반환
		else if(n == 1) return 1; // 1이면 1을 반환
		else {
			return fibonacci(n-1)+fibonacci(n-2); // 나머진 자신-1 + 자신-2 후 리턴
		}
	}
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        
        int n = in.nextInt();
        
        System.out.println(fibonacci(n));
        
        in.close()
        
    }
}

  팩토리얼과 마찬가지로 4를 예로 진행과정을 살펴보자면.

 

  1. fibonacci(4)는 fibonacci(3) + fibonacci(2)를 호출

  2. fibonacci(3)은 fibonacci(2) + fibonacci(1)을 호출

  3. fibonacci(2)는 fibonacci(1) + fibonacci(0)을 호출

  4. fibonacci(1)과 fibonacci(0)은 각각 1과 0이므로 리턴.

  3. fibonacci(2)는 1+0으로 1

  2. fibonacci(3)은 1+fibonacci(1)은 1이므로 2

  1. fibonacci(4)는 2 + 1로 3 

 

  이 과정에서 진행하는 계산과정은 결괏값이 모두 정해져 있으므로 별도의 배열로 해당 값들을 저장해두면 연산 횟수를 줄일 수 있다고 했던 거 같은데.. 위의 방법이 편하긴 하다.