[JAVA] 피보나치 수열 코딩

피보나치 수열이란?

처음 두 항을 1과 1로 한 후, 그 다음 항부터는 바로 앞의 두개의 항을 더해 만드는 수열을 의미합니다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 .....

 

그.. 유명한 피보나치 수열을 2가지 방식으로 구현 합니다.

 

1. 재귀함수를 활용

=> 재귀를 이용한 피보나치는 코드는 읽기 쉬우며, 구현도 그다지 어렵지 않습니다. 하지만 성능상의 문제가 있다는거~

   public int Fibonacci(int n) {
        // 재귀함수 활용
        if(n <= 1) 
            return 1;
        else
            return Fibonacci(n-1) + Fibonacci(n-2);
    }

 

2. 동적프로그래밍기법을 활용

=> 동적프로그래밍 : 중간중간 계산된것을 재활용하는 기법입니다. 재귀를 이용한 코딩방식보다 보기가 어려우나 성능이 빠르다는 장점이 있습니다.

public static int dynamicFibonacci(int n) {
        // 동적프로그래밍 
        int last1, last2, result = 0;
        
        if(n <= 1)
            return 1;
        
        last1 = 1;
        last2 = 1;
        
        for(int i=1; i < n; i++) {
            result = last1 + last2;
            last1 = last2;
            last2 = result;
        }
        
        return result;
    }