作者是一名沉迷于Python無法自拔的蛇友，為提高水平，把Python的重點和有趣的實例發在簡書上。
如果一個函數中所有遞歸形式的調用都出現在函數的末尾，我們稱這個遞歸函數是尾遞歸的。當遞歸調用是整個函數體中最后執行的語句且它的返回值不屬于表達式的一部分時，這個遞歸調用就是尾遞歸。尾遞歸函數的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數現代的編譯器會利用這種特點自動生成優化的代碼。
（來源于不說人話的某度）
下面是筆者的個人理解：把計算出的值存在函數內部（當然不止尾遞歸）是其計算方法，從而不用在棧中去創建一個新的，這樣就大大節省了空間。函數調用中最后返回的結果是單純的遞歸函數調用（或返回結果）就是尾遞歸。
實例
實例還是和筆者的上一篇文章相同，建議讀者閱讀 Python —— 遞歸
1、階乘
常規遞歸階乘：
|
1
2
3
4
|
def factorial(n): if n == 0: return 1 return factorial(n - 1) * n |
我們來看一下執行過程：
factorial(4)
factorial(3) * 4
factorial(2) * 3 * 4
factorial(1) * 2 * 3 * 4
factorial(0) * 1 * 2 * 3 * 4
1 * 1 * 2 * 3 * 4
1 * 2 * 3 * 4
2 * 3 * 4
6 * 4
24
但是如果把上面的函數寫成如下形式：
|
1
2
3
4
|
def factorial(n, acc=1): if n == 0: return acc return factorial(n - 1, n * acc) |
我們再看下執行過程：
factorial(4, 1)
factorial(3, 4)
factorial(2, 12)
factorial(1, 24)
factorial(0, 24)
24
很直觀的就可以看出，這次的 factorial 函數在遞歸調用的時候不會產生一系列逐漸增多的中間變量了，而是將狀態保存在 acc 這個變量中。而這種形式的遞歸，就叫做尾遞歸。
2、斐波那契數列
常規遞斐波那契數列：
|
1
2
3
4
5
|
def fib(n): if n < 2: return n else: return fib(n - 1) + fib(n - 2) |
而尾遞歸：
|
1
2
3
4
5
|
def fib_tail(n, r, t): if n == 1: return r else: return fib_tail(n - 1, t, r + t) |
一下子就充滿了逼格，還高效了許多，何樂而不為呢！
總結
可以看出，在每次遞歸調用的時候，都會產生一個臨時變量，導致進程內存占用量增大一些。這樣執行一些遞歸層數比較深的代碼時，除了無謂的內存浪費，還有可能導致著名的堆棧溢出錯誤。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://www.jianshu.com/p/7b307cc0dc2d
