재귀의 활용(피보나치 수열)

피보나치 수열은 재귀적인 형태를 띠는 대표적인 수열로서 다음과 같이 전개가 된다

 

앞의 수 두개를 더해서 현재의 수를 만들어가는 수열이다. 

 

그래서 처음 0과 1이 주어진 상태에서 다음의수 1을 만들어 가게 된다.

 

 

수열의 1번째 위치의 값은 0을 반환

 

수열의 2번째 위치의 값은 1을 반환

 

3번째 이상 n번째 부터는 n-1번째+n-2번째의 값의 합을 반환 한다.

 

이를 코드로 구현해보자

 

public class b_03_FibonacciFunc 
{
    static int Fibo(int n) 
    {
        if(n==1)//수열의 1번째 위치의 값은 0을 반환
            return 0;
        else if(n==2)//수열의 2번째 위치의 값은 1을 반환
            return 1;
        else//3번째 이상 n번째 부터는 n-1번째+n-2번째의 값의 합을 반환 한다.
            return Fibo(n-1)+Fibo(n-2);//자기자신을 다시 호출
    }
        public static void main(String[] args) 
        {
            int i;
            for(i=1; i<15; i++)
                System.out.printf("%d ", Fibo(i));
        }
}

 

 

한번쯤은 참고 해볼만한 피보나치 함수의 호출 관계를 봐보자(  fibo(7)을 실행한다고 가정 )