考慮一個添加前N個整數(shù)的簡單函數(shù)。（例如sum(5) = 1 + 2 + 3 + 4 + 5 = 15）。

這是一個使用遞歸的簡單JavaScript實現(xiàn)：

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }}

如果你打電話recsum(5)，這就是JavaScript解釋器會評估的內(nèi)容：

recsum(5)5 + recsum(4)5 + (4 + recsum(3))5 + (4 + (3 + recsum(2)))5 + (4 + (3 + (2 + recsum(1))))5 + (4 + (3 + (2 + 1)))15

請注意每個遞歸調(diào)用必須在JavaScript解釋器開始實際執(zhí)行計算總和之前完成。

這是同一函數(shù)的尾遞歸版本：

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }}

這是您調(diào)用時將發(fā)生的事件序列tailrecsum(5)（tailrecsum(5, 0)由于默認(rèn)的第二個參數(shù)，這將是有效的）。

tailrecsum(5, 0)tailrecsum(4, 5)tailrecsum(3, 9)tailrecsum(2, 12)tailrecsum(1, 14)tailrecsum(0, 15)15

在尾遞歸的情況下，每次遞歸調(diào)用的評估running_total都會更新。

注意：原始答案使用了Python中的示例。這些已經(jīng)改為JavaScript，因為現(xiàn)代JavaScript解釋器支持尾調(diào)用優(yōu)化，但Python解釋器不支持。

重要的一點是尾遞歸基本上等于循環(huán)。這不僅僅是編譯器優(yōu)化的問題，而是表達(dá)性的基本事實。這有兩種方式：你可以采取任何形式的循環(huán)

while(E) { S }; return Q

where E和Q是表達(dá)式，S是一系列語句，并將其轉(zhuǎn)換為尾遞歸函數(shù)

f() = if E then { S; return f() } else { return Q }

當(dāng)然，E，S，和Q必須定義來計算對一些變量的一些有趣的價值。例如，循環(huán)函數(shù)

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;}

相當(dāng)于尾遞歸函數(shù)

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }}sum(n) {
  return sum_aux(n,1,0);}

（這種帶有參數(shù)較少的函數(shù)的尾遞歸函數(shù)的“包裝”是一種常見的功能習(xí)慣。）