Fibonacci 数列是一个非常经典的例子，说得最通俗易懂的话就是： 1, 1, 2, 3, 5, 8, … 这样的一个数列，在数学上用数列形式表示为：$a_0 = 1$, $a_1 = 1$, $a_n = a_{n - 1} + a_{n - 2}$.

那么在计算 Fibonacci 数列这个问题上，当然大家应该都知道可以通过递推的方式来计算。

/* Fibonacci 下标从 0 开始 */
int fib(int n) {
    if (n <= 1) {
        return 1;
    }

    int f0 = 1;
    int f1 = 1;
    int t;

    for (int i = 2; i <= n; i++) {
        t = f0 + f1;
        f0 = f1;
        f1 = t;
    }

    return f1;
}

当然，以上的程序效率非常高，复杂度很明显就是：$O(n)$ .

以下我们来看看 Fibonacci 数列通过递归方式实现：

/* Fibonacci 下标从 0 开始 */
int fib(int n) {
    if (n <= 1) {
        return 1;
    }

    return fib(n - 1) + fib(n - 2);
}

当然，递归实现方式效率很慢，复杂度是：$O(2^n)$

那么本文后面将通过增加一张记录表的方式来实现递归搜索的时候能够避免重复子程序搜索。

/**
  * 快速 fibonacci 数列
  *
  * Author: L. Jiang <l.jiang.1024@gmail.com>
  */
#include <iostream>

using namespace std;

/* MAXN 给1000肯定是会溢出的，这里只是给一个例子，快速 fibonacci */
#define MAXN 1000

int fib[MAXN];

/* 初始化 */
void init() {
    for (int i = 0; i < MAXN; i++) {
        fib[i] = -1; // 因为fibonacci数列里面不可能出现-1，所以这里给每个数值都赋值为-1作为是否计算出结果的标记
    }
    fib[0] = 0;
    fib[1] = 1;
}

// 递归去搜索
// 这里不需要递归的临界判断，因为下标0和下标1都一定不为-1，一定可以return结果的。
int search_fib(int index) {
    if (-1 != fib[index]) {
        return fib[index];
    } else {
        fib[index] = search_fib(index - 1) + search_fib(index - 2);
        return fib[index];
    }
}

int main() {
    init();
    int n;
    while (scanf("%d", &n) != EOF) {
        int ans = search_fib(n);
        printf("%d\n", ans);
    }
}