The simple and most obvious way to use recursion to get the Nth term of the Fibonnaci sequence is this:

使用递归获得Fibonnaci序列第n项的最简单、最明显的方法是：

int get_term_fib(int n){    if(n == 0)        return 0;    if(n == 1)        return 1;    return get_term_fib(n - 1) + get_term_fib(n - 2);}

However, this algorithm does not scale for higher terms: for bigger and bigger n, the number of function calls that you need to make grows exponentially. This can be replaced with a simple tail recursion.

然而，这个算法不能扩展到更高的项：对于越来越大的n，需要进行的函数调用的数量呈指数增长。这可以用一个简单的尾部递归来代替。

int get_term_fib(int n, int prev = 0, int curr = 1){    if(n == 0)        return prev;    if(n == 1)        return curr;    return get_term_fib(n - 1, curr, prev + curr);}

（递归函数通常将需要迭代的变量写在参数列表中做迭代操作。）

Each call to the function now immediately calculates the next term in the Fibonnaci sequence, so the number of function calls scales linearly with n.

现在，对函数的每次调用都会立即计算Fibonnaci序列中的下一项，因此函数调用的数量与n成线性比例。

Recursive functions can get quite expensive. If they are pure functions (functions that always return the same value when called with the same arguments, and that neither depend on nor modify external state), they can be made considerably faster at the expense of memory by storing the values already calculated.

Recursion with memoization

递归函数可能会变得非常昂贵。如果它们是纯函数（当使用相同的参数调用时总是返回相同的值，并且既不依赖也不修改外部状态的函数），则可以通过存储已计算的值来大大加快它们的速度，但需要消耗内存。

The following is an implementation of the Fibonacci sequence with memoization:

以下是带记忆功能的斐波那契序列的实现：

#include <map>int fibonacci(int n){    static std::map<int, int> values;    if(n==0 || n==1)        return n;    std::map<int,int>::iterator iter = values.find(n);    if(iter == values.end())        return values[n] = fibonacci(n-1) + fibonacci(n-2);    else        return iter->second;}

（使用一个map来记录中间结果，通过查找nth项来决定如何return，如果未找到，则return values[n] = fibonacci(n-1) + fibonacci(n-2);，此时也更新了valuse[n]，如果找到则直接return iter->second;）

Note that despite using the simple recursion formula, on first call this function is O(n). On subsequent calls with the same value, it is of course O(1).

请注意，尽管使用了简单的递归公式，但第一次调用时，这个函数是O(n)。在随后使用相同值的调用中，它当然是O(1)。

Note however that this implementation is not reentrant. Also, it doesn't allow to get rid of stored values. An alternative implementation would be to allow the map to be passed as additional argument:

但是请注意，这个实现不是可重入的。而且，它不允许删除存储的值。另一种实现是允许将map作为附加参数传递：

#include <stdio.h>#include <map>int fibonacci(int n, std::map<int, int> values){    if (n==0 || n==1)        return n;    std::map<int,int>::iterator iter = values.find(n);    if (iter == values.end())        return values[n] = fibonacci(n-1,values) + fibonacci(n-2,values);    else        return iter->second;}int main(){    std::map<int,int> values;    for(int i=0;i<31;i++)        printf("%2d,  %d\n",i,fibonacci(i,values));    getchar();}/* 0,  0 1,  1 2,  1 3,  2 4,  3 5,  5 6,  8 7,  13 8,  21 9,  3410,  5511,  8912,  14413,  23314,  37715,  61016,  98717,  159718,  258419,  418120,  676521,  1094622,  1771123,  2865724,  4636825,  7502526,  12139327,  19641828,  31781129,  51422930,  832040*/

For this version, the caller is required to maintain the map with the stored values. This has the advantage that the function is now reentrant, and that the caller can remove values that are no longer needed, saving memory. It has the disadvantage that it breaks encapsulation; the caller can change the output by populating the map with incorrect values.

对于这个版本，调用方需要用存储的值维护map。这样做的好处是函数现在是可重入的，调用方可以删除不再需要的值，从而节省内存。它的缺点是破坏了封装；调用者可以通过使用不正确的值填充map来更改输出。

ref:

《C++ Notes for Professionals》

-End-