📍 피보나치 수

---

피보나치 수 𝐹𝑛 은 다음과 같이 정의할 수 있다.

𝐹𝑛 = 𝐹𝑛-1 + 𝐹𝑛-2 ( 𝑛 ∈ {2, 3, 4, … } )
➡ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ...

• 첫 번째 항과, 두 번째 항은 0과 1로 고정

✔ 재귀함수 이용

static int fibo(int N) {
	if(N < 2) return N;
    return fibo(N - 1) + fibo (N - 2);
}

✔ for문 이용

• 배열 필요

static int fibo(int N) {
	int[] arr = new int[N + 1]; // F(0) 부터 시작하므로 N + 1 크기 생성
    
    for(int i = 0; i < arr.length; i++) {
    	if(i < 2) arr[i] = i;
        else arr[i] = arr[i - 1] + arr[i - 2];
    }
}