Fibonacci Sequence   피보나치 수열

1. 피보나치 수열

  ㅇ 연속한 두 수의 합이 그 다음 수가 되는 수열
     -  {0, 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 < 1) return 0 
    else if (n == 1) return 1 
    return fib(n-1) + fib(n-2)