Fibonacci Sequence   피보나치 수열

1. 피보나치 수열

  ㅇ 연속한 두 수의 합이 그 다음 수가 되는 수열
     -  {1,1,2,3,5,8,13,21,34,55,... } 

  ㅇ 표현식 : 재귀적으로 표현 가능              ☞ 점화식 참조
     -  Fn = Fn-1 + Fn-2  또는  Fn+1 = Fn + Fn-1
        . 단, F0 = 0, F1 = 1

  ㅇ 특징
     - 커지는 속도가 거의 2n(지수시간)으로 커짐 : Fn ≒ 20.694n


2. 피보나치 수열을 구하는 알고리즘 例)

  ㅇ (재귀의 수학적 정의 그 자체를 그대로 구현한 비 효율적인 방법)
      
function fib(n)
    if n < 2 
        return 1                // f(2) = f(1) + f(0), 2 = 1 + 1
    return fib(n-1) + fib(n-2)