尾调用

尾端遞迴是一種編程技巧。遞迴函式是指一些會在函式內呼叫自己的函式，如果在遞歸函式中，递归调用返回的结果总被直接返回，則稱為尾部遞歸。尾部遞歸的函式有助將算法轉化成函數程式語言，而且從編譯器角度來說，亦容易優化成為普通迴圈。這是因為從電腦的基本面來說，所有的迴圈都是利用重複移跳到代碼的開頭來實現的。如果有尾部歸遞，就只需要疊套一個堆疊，因為電腦只需要將函數的參數改變再重新呼叫一次。利用尾部遞歸最主要的目的是要優化，例如在Scheme語言中，明確規定必須針對尾部遞歸作優化。可見尾部遞歸的作用，是非常依賴於具體實作的。

實例

通常被用於解釋遞迴的程式是計算階乘。以下計算階乘的Scheme程式不是尾端遞迴，而只是一般遞迴：

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

因此，如果呼叫factorial時的參數n足夠大，這一程式會出現堆疊溢位。然而，如果將同一程式寫作尾端遞迴，按Scheme的標準將不會出現溢位：

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

在第二個程式中，注意iter函數直接返回其遞迴呼叫，而沒有對其進行運算。因此，這是一個尾端遞迴。