文章目錄

• 1 尾遞歸簡介
• 2 總結
• 3 參考

1 尾遞歸簡介

想必大家都知道遞歸是什么，第一次接觸尾遞歸，首先要從它的定義說起：

尾遞歸：當遞歸調用是整個函數體中最后執行的語句且它的返回值不屬于表達式的一部分時，這個遞歸調用就是尾遞歸。尾遞歸函數的特點是在回歸過程中不用做任何操作。

舉一個簡單的例子，用遞歸算階乘：

int factorial(int n) { if(n == 0 || n == 1) {return 1;} else {return n * factorial(n-1); } }

現在我們模擬一下程序的過程，例如當 n = 5 的時候：

factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2))) 5 * (4 * (3 * (2 * factorial(1)))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120

上述的遞歸過程中，“最長”的部分，即代表著此刻占用的棧內存最大，所以在一般的遞歸中，它的內存占用，先是增大，后來到達一個峰值，然后縮小。

下面給出尾遞歸的實現方法，看到這段代碼后，第一印象會發現函數參數多了一個 tmp，事實上 tmp 代表著 1！（1的階乘的值）也就是 $1$ ，于是在使用函數的時候，第二個參數傳遞一個 $1$ 。

int factorial(int n, int tmp) {if(n == 0) {return 1;} else if (n == 1) {return tmp;} else {return factorial(n - 1, n * tmp);} }

我們同樣模擬一下程序的過程，例如當 n = 5 的時候：

factorial(5, 1) factorial(4, 5) factorial(3, 20) factorial(2, 60) factorial(1, 120) 120

通過這個過程，我們可以發現，它完全對應著尾遞歸的定義，即當遞歸調用是整個函數體中最后執行的語句且它的返回值不屬于表達式的一部分時，這個遞歸調用就是尾遞歸。尾遞歸函數的特點是在回歸過程中不用做任何操作。

尾遞歸比線性遞歸（第一個例子稱為線性遞歸）多一個參數，這個參數是上一次調用函數得到的結果，并且每次遞歸的時候都會保留著上次遞歸的結果，它不屬于表達式的一部分，而且它需要回歸的數據，本身已經通過參數攜帶，所以回歸過程中不用做任何操作，所以，相比較線性遞歸，尾遞歸占用的棧內存是恒定的。

2 總結

既然尾遞歸相比線性遞歸解決了線性遞歸致命的缺點（stack overflow風險），是不是更提倡使用尾遞歸呢？

答案不是的，參考數據結構與算法分析-C語言描述中的一個例子，打印一個鏈表：

/* Bad use of recursion : Printing a linked list */ /* No header */void PrintList(List L) {if (L != NULL) {PrintElement(L->Element);PrintList(L->Next);} }

在這里使用尾遞歸就是一個不好的例子，因為沒有什么需要存儲，在遞歸結束調用的時候，實際上并沒有需要存儲的值，因此，我們就可以帶著在第一次遞歸調用中已經用過的那些值， goto 到函數的頂部，下面是改進后的程序（記住，應該更加自然的使用 while 循環結果去去除尾遞歸，這里使用 goto 只是為了說明編譯器是如何自動地去除尾遞歸）。

/* Printing a linked list non-recursively */ /* Uses a mechanical translation */ /* No header */void PrintList(list L) {top:if (L != NULL) {PrintElement(L->Element);L = L->Next;goto top;} }

不用遞歸去打印一個鏈表，事實上尾遞歸的去除是如此的簡單，以至于某些編譯器可以自動完成，所以這些工作不用程序員去完成，但是即使如此，最好還是在編寫程序時避免出現尾遞歸。

3 參考

What is tail recursion - StackOverflow?

數據結構與算法分析:C語言描述(原書第2版) - Mark Allen Weiss

總結

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

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