關于尾遞歸

當一個函數調用發生時，電腦必須 “記住” 調用函數的位置 — 傳回位置，才可以在調用結束時帶着傳回值回到該位置，傳回位置一般存在調用棧上。在尾調用的情況中，電腦不需要記住尾調用的位置而可以從被調用的函數直接帶着傳回值傳回調用函數的傳回位置（相當于直接連續傳回兩次），尾調用消除即是在不改變目前調用棧（也不添加新的傳回位置）的情況下跳到新函數的一種優化（完全不改變調用棧是不可能的，還是需要校正調用棧上形參與局部變量的資訊。[2]）

對函數調用在尾位置的遞歸或互相遞歸的函數，由于函數自身調用次數很多，遞歸層級很深，尾遞歸優化則使原本 O(n) 的調用棧空間隻需要 O(1)。是以一些程式設計語言的标準要求語言實作進行尾調用消除，例如 Scheme[3][4]與 ML 家族的語言。在 Scheme 中，語言标準還将尾位置形式化，指定了各種文法中允許尾調用的地方[5]。

以 Python 為例，主要區分普通遞歸和尾遞歸對棧空間的使用[6]：

def recsum(x):
  if x == 1:
    return x
  else:
    return x + recsum(x - 1)
      

調用

recsum(5)

為例，SICP中描述了相應的棧空間變化[7][8]：

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)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
      

可觀察，堆棧從左到右，增加到一個峰值後再計算從右到左縮小，這往往是我們不希望的，是以在C語言等語言中設計

for, while, goto

等特殊結構語句，使用疊代、尾遞歸，對普通遞歸進行優化，減少可能對記憶體的極端消耗。修改以上代碼，可以成為尾遞歸：

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)
      

或者使用疊代：

for i in range(6):
  sum += i
      

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