使用尾递归和 Fibonnaci 式递归来解决 Fibonnaci 序列

使用递归来获得 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);
}

但是，此算法不能扩展到更高的术语：对于越来越大的 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);
}

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