피보나치 수열 구현 두가지 방법

피보나치 수열이란?

피보나치 수열은 앞의 두 개의 수를 더한 값을 다음 값으로 넣는 방식이다.

예를 들어 다음과 같이 리스트에 숫자 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 (꼬리 재귀)

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) 실행 시간에 실행된다.
 

1번 Binary Recursive에 경우 함수안의 자신의 함수를 2번 부른다.

받는 숫자 n이 커질수록 재귀 호출을 두 번 이상 부르므로 함수 호출 횟수가 방대하게 증가하는 문제가 발생하고, 

재귀 호출 깊이가 깊어지면 Stack을 많이 사용하는 문제가 발생한다.

2번 Tail Recursive에 경우 함수안의 자신의 함수를 1번 부른다.

Tail Recursion 를 쓰거나 반복 방식을 사용하면 Binary Recursive의 시간복잡도 및 Stack 사용을 줄일 수 있다.

마지막으로 소스를 첨부한다.

Pibonachi.java