먼저 아래는 Recursive 방식으로 피보나치 함수를 작성한 예이다. 단점으로 만약 입력 파라미터 n 값이 큰 수라면, 성능상 문제가 발생한다. 이러한 방식으로는 O(2**N) 의 시간을 소요된다.

int Fib(int n)
{
    return n <= 1 ? n : Fib(n - 1) + Fib(n - 2);
}

위의 문제점을 보완하기 위해 Dynamic Programming의 Memoization 개념을 도입하여 O(N)이 소요되는 빠른 피보나치 함수를 아래와 같이 구현할 수 있다. 기본적으로 한번 계산된 결과를 해시 테이블에 저장하고 Fib() 함수 호출전에 미리 기존 결과를 해시테이블에서 먼저 체크하기 때문에 속도 향상을 할 수 있다.

using System.Collections.Generic;

namespace Fibo
{
    class Class1
    {
       Hashtable memo = new Hashtable();        

       public int Fib(int n)
       {
          int f;

          if (memo.ContainsKey(n)) return (int)memo[n];
            
          if (n <= 1) f = n;
          else f = Fib(n - 1) + Fib(n - 2);

         memo.Add(n, f);
         return f;
        }    
     }
}

그리고 마지막으로 아래는 Iterative 방식으로 Bottom-up 방식으로 F(1), F(2), ..., F(N) 까지 루프를 돌며 차례로 피보나치를 계산하고 이전 결과를 배열에 저장하기 때문에 O(N)의 빠른 속도를 낼 수 있다.

public int Fib(int n)
{
    int[] F = new int[n + 1];

    for (int i = 0; i <= n; i++)
    {
        if (i <= 1) F[i] = i;
        else F[i] = F[i - 1] + F[i - 2];
    }

    return F[n];
}