使用尾遞迴和 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 成線性比例。