피보나치치 수열(Fibonacci Sequence)은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 말한다.
▲ (출처: https://blogs.glowscotland.org.uk/glowblogs/jypetrieuodep/2018/10/09/fibonacci-sequence-significant-coincidence/)
피보나치 수열을 구현하기 위한 방법이 몇가지 존재하는데 여기서는 재귀함수를 이용하도록 하겠다.
재귀함수(Recursive Function)란? 글을 읽어보면 재귀함수에는 재귀가 수렴해야 할 베이스케이스와 재귀케이스가 있어야 하는데 0번째 항부터 피보나치 수열을 시작할 경우 베이스케이스와 재귀케이스는 아래와 같다.
베이스케이스 : F0 = 0 and F1 = 1
재귀케이스 : Fn = Fn-1 + Fn-2, ( n ∈ { 2,3,4, ...} )
재귀케이스 : Fn = Fn-1 + Fn-2, ( n ∈ { 2,3,4, ...} )
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public class Main {
public static void main(String[] args) {
System.out.println(fibonacci(8)); // 21
}
private static int fibonacci(int n) {
if(n < 2) {
return n ;
}
return fibonacci(n-1) + fibonacci(n-2);
}
}
Colored by Color Scripter
|
레퍼런스
'알고리즘(Algorithm) > 재귀(recursion)' 카테고리의 다른 글
| (재귀)N-Queen 문제 (0) | 2019.06.25 |
|---|---|
| (재귀)Blob(Labeling) 알고리즘 (0) | 2019.06.25 |
| (재귀)미로(MAZE)찾기 (0) | 2019.06.25 |
| 재귀함수(Recursive Function)란? (0) | 2019.06.25 |
