[알고리즘]피보나치 수열과 재귀함수를 이용한 알고리즘_java

f(n) = f(n-1)+f(n-2)

**f(1) = 1

**f(2) = 2

 

1. 재귀함수

    public int solution(int N){
        if(N <= 2){
            return N;
        }
        return solution(N-1)+solution(N-2);
    }

 

2. 피보나치 수열

	public int solution2(int N){
        int a = 1;
        int b = 2;

        if(N==1){
            return a;
        }

	//a = f(n-1)
        //b = f(n)
        for(int i =3 ; i <= N; i++){
            int temp = a+b;
            a = b;
            b = temp;
        }
        return b;
        
    }

 

그림으로 이해하는 피보나치 수열♡♥♣♪♥♤♥

ex) f(4)