階乘函數：
n!=n*(n-1)*(n-2)...3*2*1
針對這樣的表述，直譯成一個過程：
(define (factorial n)
??? (if (=n 1)
??????? 1
??????? (* n (factorial (- n 1)))))
如果是factorial(6),其計算行為是：
(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720
現在我們換種不同的角度來計算階乘，我們可以將計算階乘n!的規則描述為：先乘以1和2，而后將得到的結果乘以3，而后再乘以4，這樣下去直到達到n.更形式的說，我們要維護一個變動的乘積product,以及一個從1到n的計數器counter,這一計算過程可以描述為counter和product的如下變化，從一步到下一步，它們都按照下面的規則變化：
product <- counter*product
counter <- counter-1
可以看到，n!也就是計算器counter超過n時乘積product的值。
這樣，我們可以這樣描述階乘的過程：
(define (factorial n)
?? (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
? (if (> counter max-count)
????? product
????? (fact-iter? (* counter product)
????????????????? (+ counter 1)
????????????????? max-count)))
這樣，新的模型的6!的計算過程：
(factorial 6)
(factorial 1 1 6)
(factorial 1 2 6)
(factorial 2 3 6)
(factorial 6 4 6)
(factorial 24 5 6)
(factorial 120 6 6)
(factorial 720 7 6)
720

考慮前一個計算過程，代換模型揭示出一種先逐步展開而后收縮的形狀，在展開的過程里，這一計算過程構造起一個推遲進行的操作所形成的鏈條，收縮階段表現為這些運算的實際執行。這種類型的計算過程由一個推遲執行的運算鏈條刻畫，稱為一個遞歸計算過程。要執行這樣的計算過程，解釋器就需要維護好那些以后將要執行的操作的軌跡。在計算階乘n!時，推遲執行的乘法鏈條的長度也就是為了保存其軌跡需要保存的信息量，這個長度隨著n值而線性增長，就像計算中的步驟數目一樣。這樣的計算過程稱為一個線性遞歸過程。
與之相對應，第二個計算過程里并沒有任何增長或者收縮。對于任何一個n，在計算過程中的每一步，在我們需要保存軌跡里，所有的東西就是變量counter， product和max-count的當前值。我們稱這種過程為一個迭代計算過程。一般來說，迭代計算過程就是那種其狀態可以用固定數目的狀態變量描述的計算過程；而與此同時，又存在著一套固定的規則，描述了計算過程在從一個狀態到下一狀態轉換時，這些變量的更新方式，還有一個結束檢測，它描述這一計算過程應該終止的條件。在計算n!時，所需的計算步驟隨著n線性增長，這種過程稱為線性迭代過程。
我們還可以從另一個角度來看這兩個過程之間的對比。在迭代的情況里，在計算過程中的任何一點，那幾個程序變量都提供了有關計算狀態的一個完整描述。如果我們令上述計算在某兩步之間停下來，要想重新喚醒這一計算，只需為解釋器提供有關這三個變量的值。而對于遞歸計算過程而言，這里還存在著另外的一些隱含信息，它們并未保存在程序變量里，而是由解釋器維持著，指明了在所推遲的運算所形成的鏈條里的漫游中，“這一計算過程處在何處”。這個鏈條越長，需要保存的信息也就越多。
在做迭代與遞歸之間的比較時，我們必須小心，不要搞混了遞歸計算過程的概念和遞歸過程的概念。當我們說一個過程是遞歸的時候，論述的是一個語法形式上的事實，說明這個過程的定義中（直接或間接地）引用了該過程本身。在說某一計算過程具有某種模式時（如線性遞歸），我們說的是這一計算過程的進展方式，而不是相應過程書寫上的語法形式。當我們說某個遞歸過程將產生出一個迭代的計算過程時，別奇怪，上面的第二種方式就是，其事先稱為尾遞歸。（某些語言某些編譯器可能會直接將其優化為循環之類的動作）

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的递归 尾递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。