피보나치 수열이란?
피보나치 수열은 앞의 두 개의 수를 더한 값을 다음 값으로 넣는 방식이다.
예를 들어 다음과 같이 리스트에 숫자 2개 0,1 이 있다고 해보자.
그다음 숫자는 0과 1을 더한 1이 리스트에 추가된다. 그다음 숫자는 1과 1을 더한 2가 리스트에 추가된다.
0, 1 then 0+1 = 1
then 0, 1, 1
0, 1, 1 then 1+1 = 2
then 0, 1, 1, 2
0, 1, 1, 2 then 1+2 = 3
then 0, 1, 1, 2, 3 ...
이런 방식으로 추가하면 다음과 같은 리스트가 될 것이다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 ...
피보나치 수열 구현하는 방식을 두 가지 방법으로 표현하였다.
1. Binary Recursive (이진 재귀)
2. Tail-end Recursive (꼬리 재귀)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | package test1; public class Pibonachi { public static void main(String[] args) { // TODO Auto-generated method stub MyFib1 myfib1 = new MyFib1(); System.out.println("myfib1 value: "+myfib1.fib(5)); MyFib2 myfib2 = new MyFib2(); System.out.println("myfib2 value: "+myfib2.fib(5)); } } // 피보나치 수열 두가지 방법 // 1. Binary Recursive 이진 재귀 // f(n) = f(n - 1) + f(n - 2) 재귀 함수를 두번 실행 class MyFib1{ public int fib(int n) { if (n < 2){ return n; }else{ System.out.println("call fib("+(n-1)+")"+"+"+"call fib("+(n-2)+")"); return fib(n - 1) + fib(n - 2); } } } // (F(n)) 실행 시간에 실행되며, Ω(1.6n)의 시간을 갖는다. // 2. Tail-end Recursive 꼬리 재귀 // f(n - 1, fibo1 + fibo2, fibo1)로 재귀함수를 한 번만 실행 class MyFib2{ long fib(long n) { return fibo_iter(n, 0, 1); } long fibo_iter(long x, long a, long b) { // 5, 0, 1 if (x==0) return a; else return fibo_iter(x-1, b, a+b); // 4, 1, 1 // 3, 1, 2 // 2, 2, 3 // 1, 3, 5 // 0, 5, 8 => 5 } } // Θ(n) 실행 시간에 실행된다. | cs |
1번 Binary Recursive에 경우 함수안의 자신의 함수를 2번 부른다.
받는 숫자 n이 커질수록 재귀 호출을 두 번 이상 부르므로 함수 호출 횟수가 방대하게 증가하는 문제가 발생하고,
재귀 호출 깊이가 깊어지면 Stack을 많이 사용하는 문제가 발생한다.
2번 Tail Recursive에 경우 함수안의 자신의 함수를 1번 부른다.
Tail Recursion 를 쓰거나 반복 방식을 사용하면 Binary Recursive의 시간복잡도 및 Stack 사용을 줄일 수 있다.
마지막으로 소스를 첨부한다.
Pibonachi.java'전체 > 알고리즘' 카테고리의 다른 글
| 문자열 거꾸로 출력하기 (0) | 2017.12.13 |
|---|---|
| 최대공약수 최소공배수 구하기 (0) | 2017.12.13 |
| 하노이의 탑 구현 (0) | 2017.12.12 |
| 자바 배열 최대값 구하기, 배열 중복되는 값 구하기 (0) | 2017.12.12 |
| n값을 받아 1부터 n까지의 합계 구하기 (0) | 2017.12.11 |
StackProblem.zip
