尾遞歸

概念

如果一個(gè)函數(shù)中所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾，我們稱這個(gè)遞歸函數(shù)是尾遞歸的。當(dāng)遞歸調(diào)用是整個(gè)函數(shù)體中最后執(zhí)行的語(yǔ)句且它的返回值不屬于表達(dá)式的一部分時(shí)，這個(gè)遞歸調(diào)用就是尾遞歸。尾遞歸函數(shù)的特點(diǎn)是在回歸過程中不用做任何操作，這個(gè)特性很重要，因?yàn)榇蠖鄶?shù)現(xiàn)代的編譯器會(huì)利用這種特點(diǎn)自動(dòng)生成優(yōu)化的代碼。

原理

當(dāng)編譯器檢測(cè)到一個(gè)函數(shù)調(diào)用是尾遞歸的時(shí)候，它就覆蓋當(dāng)前的活動(dòng)記錄而不是在棧中去創(chuàng)建一個(gè)新的。編譯器可以做到這點(diǎn)，因?yàn)檫f歸調(diào)用是當(dāng)前活躍期內(nèi)最后一條待執(zhí)行的語(yǔ)句，于是當(dāng)這個(gè)調(diào)用返回時(shí)棧幀中并沒有其他事情可做，因此也就沒有保存棧幀的必要了。通過覆蓋當(dāng)前的棧幀而不是在其之上重新添加一個(gè)，這樣所使用的棧空間就大大縮減了，這使得實(shí)際的運(yùn)行效率會(huì)變得更高。

?

內(nèi)存中的棧

在計(jì)算機(jī)系統(tǒng)中，棧是一個(gè)具有以上屬性的動(dòng)態(tài)內(nèi)存區(qū)域(雖然與數(shù)據(jù)結(jié)構(gòu)中的棧有區(qū)別，但是它們的思想都是先進(jìn)后出)。程序可以將數(shù)據(jù)壓入棧中，也可以將數(shù)據(jù)從棧頂彈出。在i386機(jī)器中，棧頂由稱為esp的寄存器進(jìn)行定位。壓棧的操作使得棧頂?shù)牡刂窚p小，彈出的操作使得棧頂?shù)牡刂吩龃蟆Ｔ诔绦虻倪\(yùn)行中有著舉足輕重的作用。最重要的是棧保存了一個(gè)函數(shù)調(diào)用時(shí)所需要的維護(hù)信息，這常常稱之為堆棧幀或者活動(dòng)記錄。堆棧幀一般包含如下幾方面的信息：

(1)函數(shù)的返回地址和參數(shù)

(2)臨時(shí)變量：包括函數(shù)的非靜態(tài)局部變量以及編譯器自動(dòng)生成的其他臨時(shí)變量。

?

棧在函數(shù)調(diào)用過程中的工作原理

int?main() {foo1();foo2();return 0; }

上面是一個(gè)簡(jiǎn)單的示例代碼，現(xiàn)在簡(jiǎn)單的模擬一下這個(gè) main 函數(shù)調(diào)用的整個(gè)過程，$ 字符用于表示占地：

(1)建立一個(gè)函數(shù)棧。 $

(2)main 函數(shù)調(diào)用，將 main 函數(shù)壓進(jìn)函數(shù)棧里面。$ [main]

(3)做完了一些操作以后，調(diào)用 foo1 函數(shù)，foo1 函數(shù)入棧。$ [main]?[foo1]

(4)foo1 函數(shù)返回并出棧。$ [main]

(5)做完一些操作以后，調(diào)用 foo2 函數(shù)，foo2 函數(shù)入棧。$ [main]?[foo2]

(6)foo2 函數(shù)返回并出棧。$ [main]

(7)做完余下的操作以后，main函數(shù)返回并出棧。$

上面這個(gè)過程說明了棧的作用。就是在第 4 和第 6 步，讓 foo1 和 foo2 函數(shù)執(zhí)行完了以后能夠在回到 main 函數(shù)調(diào)用 foo1 和 foo2 原來的地方。這就是棧，這種"先進(jìn)后出"的數(shù)據(jù)結(jié)構(gòu)的意義所在。

?

尾遞歸實(shí)例

要講尾遞歸，要先從遞歸講起。最簡(jiǎn)單的例子——階乘。

以下是一個(gè)用線性遞歸寫的計(jì)算 n 的階乘的函數(shù)：

int fact(int n) //線性遞歸 {if (n < 0)return 0;else if(n == 0 || n == 1)return 1;elsereturn n * fact(n - 1); }

普通遞歸的問題在于展開的時(shí)候會(huì)產(chǎn)生非常大的中間緩存，而每一層的中間緩存都會(huì)占用寶貴的棧的空間，所以導(dǎo)致了當(dāng)這個(gè) n 很大的時(shí)候，棧上空間不足則會(huì)產(chǎn)生"爆棧"的情況。

當(dāng)n=5時(shí)，線性遞歸的遞歸過程如下:

fact(5) {5*fact(4)} {5*{4*fact(3)}} {5*{4*{3*fact(2)}}} {5*{4*{3*{2*fact(1)}}}} {5*{4*{3*{2*1}}}} {5*{4*{3*2}}} {5*{4*6}} {5*24} 120

?

n 的階乘的尾遞歸函數(shù)：

int facttail(int n, int a) //尾遞歸 {if (n < 0)return 0;else if (n == 0)return 1;else if (n == 1)return a;elsereturn facttail(n - 1, n * a); }

當(dāng)n=5時(shí)，尾遞歸的遞歸過程如下：

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

?

誤區(qū)

跟上面的普通遞歸函數(shù)比起來，貌似尾遞歸函數(shù)因?yàn)樵谡归_的過程中計(jì)算并且緩存了結(jié)果，使得并不會(huì)像普通遞歸函數(shù)那樣展開出非常龐大的中間結(jié)果，所以不會(huì)爆棧？答案：當(dāng)然不是！尾遞歸函數(shù)依然還是遞歸函數(shù)，如果不優(yōu)化依然跟普通遞歸函數(shù)一樣會(huì)爆棧，該展開多少層依舊是展開多少層。不會(huì)爆棧是因?yàn)檎Z(yǔ)言的編譯器或者解釋器所做了"尾遞歸優(yōu)化"，才讓它不會(huì)爆棧的。

?

階乘函數(shù)及gdb調(diào)試

將上述2個(gè)階乘代碼進(jìn)行編譯，并對(duì)兩種方法進(jìn)行調(diào)試，觀察在程序運(yùn)行過程中棧幀的使用情況以及程序的運(yùn)行情況。以下會(huì)使用的gdb調(diào)試命令：

編譯：gcc/g++ test.c -g -o test 運(yùn)行：gdb test list+行號(hào) 查看程序指定行附近的代碼 b +行號(hào) 在該行添加斷點(diǎn) r ?????????? 運(yùn)行程序 n ?????????? 逐步運(yùn)行程序 bt?????????? 打印調(diào)用棧的使用情況 info frame?? 查看當(dāng)前棧幀的情況

代碼：

#include <bits/stdc++.h> using namespace std; #define M 5int fact(int n) //線性遞歸 {if (n < 0)return 0;else if(n == 0 || n == 1)return 1;elsereturn n * fact(n - 1); }int facttail(int n, int a) //尾遞歸 {if (n < 0)return 0;else if (n == 0)return 1;else if (n == 1)return a;elsereturn facttail(n - 1, n * a); }int facttail1(int n, int a) //尾遞歸轉(zhuǎn)化為循環(huán) {while(n > 0){a = n * a;n--;}return a; }int main() {//printf("%p", facttail);int a = fact(M);int b = facttail(M, 1);cout << "A:" << a <<endl;cout << "B:" << b <<endl; }

?

非尾遞歸階乘的調(diào)試情況：

(1)使用 b 設(shè)置斷點(diǎn)并運(yùn)行

(2)使用 bt 命令查看棧的使用情況

(3)遞歸層層返回

?

尾遞歸階乘的調(diào)試情況：

上述的尾遞歸階乘函數(shù)并未優(yōu)化，所以兩個(gè)階乘函數(shù)展開的層數(shù)還是一樣的。但是兩者還是有不一樣的地方，從上圖中可以看出，尾遞歸階乘函數(shù)在運(yùn)行到最后時(shí)，它是直接返回相應(yīng)的值。而非尾遞歸階乘函數(shù)是層層深入然后再一層層地返回，最后得到結(jié)果。在這一過程中可以使用info frame命令查看更為詳細(xì)的棧幀信息。

所有遞歸都能等效于循環(huán)＋棧(例如：數(shù)據(jù)結(jié)構(gòu)中的非遞歸前、中、后序遍歷)，尾遞歸只是只是恰好是那種沒有找的最簡(jiǎn)單的情況。遞歸之所以能寫出比循環(huán)可讀性高的代碼是因?yàn)檫f歸隱含了一個(gè)棧，而用循環(huán)實(shí)現(xiàn)的時(shí)候需要手動(dòng)維護(hù)一個(gè)棧導(dǎo)致代碼很長(zhǎng)，但是尾遞歸恰好就是那個(gè)不需要這個(gè)棧的特殊情況，也就是說這個(gè)時(shí)候遞歸相對(duì)于循環(huán)完全沒有任何優(yōu)勢(shì)了。對(duì)于無棧循環(huán)不能等效的遞歸函數(shù)，轉(zhuǎn)化成尾遞歸比轉(zhuǎn)化成有棧循環(huán)更難看并且還更慢。

?

快排尾遞歸優(yōu)化及gdb調(diào)試

以下將使用兩種快排的方法，即尾遞歸優(yōu)化的快排和普通快排。通過對(duì)兩種方法的調(diào)試，觀察程序運(yùn)行過程中棧的使用情況。將尾遞歸優(yōu)化成迭代的關(guān)鍵：

1.代碼主體是根據(jù)基準(zhǔn)值完成排序后再遞歸調(diào)用函數(shù)。

2.將參數(shù) low 提取出來，使其成為迭代變量。

3.將原來函數(shù)的里面所代碼寫在一個(gè) while (true) 里面。

4.遞歸終止的 return 不變，這里當(dāng)low >= high時(shí)遞歸終止。

代碼：

#include <stdio.h>int Partition(int a[], int low, int high) {int i,j,k,temp;i = low;j = high+1;k = a[low];while(1){while(a[++i] < k && i < j);while(a[--j] > k);if(i >= j) break;else{temp = a[i];a[i] = a[j];a[j] = temp;}}a[low] = a[j];a[j] = k;return j; }void QuickSort(int a[], int low, int high) {if(low < high){int q = Partition(a, low, high);QuickSort(a, low, q-1);QuickSort(a, q+1, high);} }void QuickSort1(int a[], int low, int high) {int pivotPos;while(low < high){pivotPos = Partition(a,low,high);QuickSort(a,low,pivotPos-1);low = pivotPos + 1;} }int main() {int i;int a[10] = {3,4,5,6,1,2,0,7,8,9};int b[10] = {3,4,5,6,1,2,0,7,8,9};QuickSort(a, 0, 9);QuickSort1(b, 0, 9);for(i = 0; i < 10; ++i){printf("[%d]", a[i]);}printf("\n");for(i = 0; i < 10; ++i){printf("[%d]", b[i]);}printf("\n");return 0; }

?

普通快排調(diào)試情況：

(1)使用 b 設(shè)置斷點(diǎn)并運(yùn)行，在這一過程中注意參數(shù) low 、high 和棧的變化

(2)運(yùn)行過程中參數(shù)的變化以及棧最深的情況

?

尾遞歸優(yōu)化的快排調(diào)試情況：

(1)使用 b 設(shè)置第42行代碼為斷點(diǎn)并運(yùn)行，在這一過程中注意參數(shù) low 、high 和棧的變化

(2)接下來都是逐步運(yùn)行并觀察參數(shù)和棧的使用情況

(3)最后一步運(yùn)行完，返回 main 函數(shù)

從上圖中可以明顯看出，尾遞歸優(yōu)化的快排使用的棧空間很少，因?yàn)樵摲椒ㄊ褂玫媪诉f歸操作。當(dāng)數(shù)據(jù)量足夠大時(shí)，使用尾遞歸優(yōu)化后，可以縮減堆棧的深度，由原來的O(n)縮減為O(logn)。

?

總結(jié)

關(guān)于尾遞歸的問題，網(wǎng)上有許多資料，但大多都是將問題敘述了一遍，也沒有提及優(yōu)化的過程。百度百科中以階乘函數(shù)的尾遞歸為例向大家介紹了這個(gè)問題，但是結(jié)論中有一個(gè)表述是：可以減少棧的深度。(1)這個(gè)表述是有問題的，經(jīng)過對(duì)代碼的調(diào)試(沒有進(jìn)行優(yōu)化)，發(fā)現(xiàn)兩種階乘方法遞歸的深度是一樣的。(2)需要對(duì)代碼進(jìn)行尾遞歸優(yōu)化才能達(dá)到減少棧的深度的目的。如果發(fā)現(xiàn)類似的問題，建議大家調(diào)試相應(yīng)的程序，查看棧的使用情況。

參考：https://zhuanlan.zhihu.com/p/36587160

總結(jié)

以上是生活随笔為你收集整理的尾递归及快排尾递归优化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。