看了自己的動態記錄，發現自己已經遺忘了曾經的自己，有一條動態，2013年的時候，我看了一篇關于尾遞回的博文，那時候還只是一個初學者，胡亂評論了一下，作者希望我能寫一篇博文發表一下自己的看法，當時沒有寫，然而現在卻想寫點什么總結一下，不保證說的沒問題，只希望如果有像我當年一樣的初學者看到，可以參考借鑒，或許能有些幫助，在此也感謝給我啟發，教會我知識的陌生朋友們，
1. 遞回就是一個函式直接或間接的自己呼叫自己，間接就是f0 -> f1 -> f0 ->f1這種，但也就是一個名詞而已，并不神奇，它只是一個普普通通的函式呼叫，但由于自己呼叫自己這個特性，有一種自動化的力量，給它一個規則，它可以自動的持續運行下去，直到觸發停止條件，一個遞回函式就像是一個簡單的計算機，
2. 所有的遞回都可以用回圈來替代，所有的回圈也都可以用遞回來替代，兩者是等價的，
3. 遞回是人腦的直接思維方式，回圈是當前多數(我所知道的所有的)cpu的直接思維方式，
4. 對于cpu來講，函式呼叫只是暫存器，記憶體，跳轉等操作，如果不涉及額外堆疊空間使用（極簡單函式的特殊情況），函式呼叫和回圈的差別可能僅僅是使用的暫存器不同，
5. 遞回可以把復雜的問題變得簡單，是一種處理問題的模型，比如漢諾塔，快速排序，二叉樹遍歷和查找，如果學會使用遞回這種思維方式思考問題，很多問題會變得很簡單，大事化小，小事化了，每一步都是很簡單的操作，
6. 正確的思維會使問題很簡單，錯誤的思維會讓人發懵，使用遞回的思考方式是忘記呼叫的是自己，自己呼叫的是任意一個函式，那個函式有沒有實作，是否實作得正確不是我現在要關心的事，我只要保證，在那個函式正確實作的前提下，我現在寫的這個函式是沒問題的，當我寫完當前函式的時候，被呼叫的函式也就寫完了(副產物)，因為它們是同一個，這有點像數學歸納法，
7. 正確的實作一個遞回函式，需要保證有退出的條件，除非你是在寫一個死回圈，同時隨著遞回層數變深，問題逐漸簡單化，規模逐漸縮小，或者是向退出條件逼近(收斂)，
8. 遞回對堆疊空間的占用分兩種，尾遞回開啟相應的優化之后不會導致堆疊空間使用不停擴大，非尾遞回對堆疊空間的呼叫要看遞回的層數，遞回層數是可預測的，一般二分的遞回(理想的情況，極端的情況二叉樹會變成鏈表，這時候已經不是二分法了，但二叉樹是可以事先保證平衡的)層數大約為log2(n)，30層函式呼叫使用的堆疊空間很少(使用超級龐大的陣列區域變數這樣的特殊情況除外)，但是n是10億級別，這個時候要關注的已經不是堆疊空間了，而是保存資料的記憶體空間或cpu等資源，比如用遞回方法計算Fibonacci數列，現在的個人電腦默認堆疊空間(M級別)，不可能堆疊溢位的，忙不過來的是cpu，多分的情況堆疊空間一般都不會過深，原因是一邊呼叫增加深度，一邊回傳減少深度，用完全平衡二叉樹為例，畫一個圖看一下呼叫程序就一目了然，
下面就堆疊空間的使用，尾遞回，遞回回圈的轉換等問題詳細分析，
除非是特殊的情況，編譯器能優化成不使用堆疊空間，否則遞回是需要堆疊空間的，這和任何一個函式呼叫都是一樣的，對于解決實際問題的函式，一般沒有不需要堆疊空間的，在函式呼叫的時候，需要保存cpu暫存器到堆疊空間（用于恢復函式的執行），區域變數也有可能會導致堆疊空間的使用，每一個函式執行的時候區域變數都會占用一次堆疊空間，每一次函式呼叫也會觸發一次堆疊空間的使用，這就是每一次遞回呼叫的堆疊空間代價，函式呼叫總是有呼叫就有回傳的，最大代價就是最大遞回層數，尾遞回是一種特殊情況，考慮下面的函式，
int f(int n) { if(n <= 0) return n; // body; return f(n-1); }
return f(n-1);是函式f的最后一個陳述句，f(n-1)的回傳值就是f(n)的回傳值，也就是說對于當前函式f(n)已經沒有必要保存現場了，它的堆疊空間不需要恢復了，f(n-1)回傳到f(n)，f(n)再向上回傳，那為什么要留個中介呢，為什么不直接向上回傳呢，所以堆疊空間中保存的回傳地址等不動，進入f(n)時保存的暫存器(callee-saved registers)不動，也就是f(n)的上層現場不動，他們直接繼承給f(n-1)，f(n-1)不再
保存它的回傳地址(f(n)的最后)，也不再保存使用的暫存器(f(n)已經不需要恢復了)，f(n)的區域變數使用的堆疊空間直接被f(n-1)的給覆寫掉，同樣的邏輯再向上遞推，會發現，每一層函式呼叫引起的堆疊空間占用都相當于沒有了，實際上上述代碼就變成了
int f(int n) { while( n > 0 ) { //body; n--; } return n; }
這種遞回叫做尾遞回，即遞回呼叫之后不需要再有額外的操作，并且遞回之前沒有其他遞回呼叫，開啟優化之后（gcc, O2默認開啟）編譯器可以將尾遞回優化成回圈，
再考慮下面的函式
int f(int n) { if(n <= 0) return n; // body; return n + f(n-1); }
這種遞回呼叫是無法 直接 變成回圈的，這里用直接，是因為這種情況太簡單了，編譯器不會那么傻，gcc O1就會變成回圈，為什么不能直接變成回圈呢，因為f(n-1)之后還有其他操作（回傳值+n），為了繼續其他操作能夠繼續執行，呼叫f(n-1)之前需要保存現場，需要用到堆疊空間，每一層呼叫都會保存一次堆疊空間，這時候堆疊空間的占用是O(n)的，因為不是二分，三分，n的數量稍大一點就會導致堆疊溢位，當然這里實在是太簡單了！換個復雜的，編譯器就不會優化了（只是寫本文的時候用的gcc，不排除以后編譯器越來越智能的可能），
unsigned long fib(int n) { if(n < 2) return 1; return fib(n-1) + fib(n-2); }
fib(3) 呼叫 fib(2)和fib(1)，假定編譯器生成的指令是先呼叫fib(2)，那么就要在堆疊空間中保存現場，以便fib(2)回傳的時候能夠繼續執行fib(1)和一個加法操作，fib(2)呼叫fib(1)和fib(0)，還是假定先呼叫左邊的，呼叫fib(1)的時候需要保存現場，然后回傳1, 恢復現場，保存現場，呼叫fib(0)，然后恢復現場，加法運算，然后再回傳上層，即fib(2)回傳，恢復現場，fib(2)下面的所有呼叫占用的堆疊空間都已釋放了(遞減堆疊堆疊頂暫存器數值增加)，然后保存現場，呼叫fib(1)，回傳1, 恢復現場，加法運算，回傳，整個fib(3)就是這樣完成的，可見每次呼叫+左邊的分支的時候，遞回層數會增加一層，每次呼叫+右面的分支的時候，左面增加的層數都已經恢復，這是一個動態增減的程序，遞回層數是有限的，這種Fibonacci數列演算法慢的根源在于重復計算，不重復計算的方法如下：
unsigned long fib2(int n, unsigned long left, unsigned long right) { if( n < 2 ) return right; return fib2(n - 1, right, left+right); }
這里是一個尾遞回，相當于回圈, 當然如果不優化，堆疊空間占用是O(n)，n足夠大是會溢位的，
可見，回圈和尾遞回是直接互相轉換的，回圈變數相當于函式中的引數，回圈退出條件相當于函式退出的條件，回圈變數的增減相當于引數傳遞時的增減計算，回圈體相當于函式體，所以像scheme這樣的編程語言沒有回圈但是并不影響表達能力，
Fibonacci數列回圈的演算法是從數列的左邊開始，不符合直觀定義，需要知道原理才能想到，直觀的定義是從右到左，然而左邊又沒有準備好，所以需要借用堆疊，
考慮一個更明顯的例子，單向非回圈鏈表的正向遍歷和逆向遍歷，前者是尾遞回(回圈)，后者非尾遞回(使用回圈需要借助堆疊)，正向遍歷不需要額外的堆疊空間，但是如何實作逆向遍歷呢？首先要拿到最后一個節點，但是訪問完最后一個節點了，到哪里去找上一個節點呢，單向鏈表并沒有prev指標，很明顯，需要在記憶體中保存，由于訪問的順序是后進先出，用的應該是堆疊這種模型，而函式呼叫本來就是堆疊的模型的，所以如果使用函式呼叫的方式是很自然的，很符合人的思維邏輯的，用遞回的方式都不用考慮堆疊的問題，因為這是一種很自然的符合人的邏輯的思考模型，代碼如下：
struct list{ int c; struct list *next; }; #define print_list(list) (void)list void visit(const struct list *cur) { if(cur == NULL) return; print_list(cur); visit(cur->next); } void visit_reverse(const struct list *cur) { if(cur == NULL) return; // 訪問后面的，怎么訪問的不用管，會有人保證它的逆序 visit_reverse(cur->next); // 后面的全都訪問完了，訪問當前的 print_list(cur); } #define list_append(tail_p, cur) ((*tail_p)->next = cur, (*tail_p) = cur) struct list * _list_reverse(struct list *cur, struct list **tail_after_reverse) { // 最后一個 if(cur->next == NULL) { // 記錄末尾，方便list_append *tail_after_reverse = cur; return cur; } struct list *head = _list_reverse(cur->next, tail_after_reverse); list_append(tail_after_reverse, cur); return head; } // 逆序單向鏈表 struct list * list_reverse(struct list *cur) { struct list *tail_after_reverse; if(cur == NULL) return cur; struct list *head = _list_reverse(cur, &tail_after_reverse); list_append(&tail_after_reverse, NULL); return head; }
尾遞回和回圈可以互相轉換，這是很明顯的，那么非尾遞回如何和回圈互相轉換呢，理論上是一定可以完成的，因為對于cpu來講遞回就是用堆疊來實作的，下面以二叉樹的先序，中序，后序的遍歷方式來舉例說明，不過能夠實作不代表應該這樣做，代碼的可讀性和見解性非常重要，并且轉變成回圈也未必就能感受到性能的變化，
#include <assert.h> #include <stdio.h> struct tree{ int n; struct tree *left; struct tree *right; }; static const void *stack[128]; static char stack_flag[128]; static int stack_i; #define visit(t) printf("%d\t", t->n) #define push(x) do{if(x) stack[stack_i++] = x;}while(0) #define pop() (stack_i == 0 ? NULL : stack[--stack_i]) #define push2(x, flag) do{if(x) {stack[stack_i] = x; stack_flag[stack_i++] = flag;}}while(0) #define pop2(flag) (stack_i == 0 ? NULL : ((flag=stack_flag[--stack_i]), (stack_flag[stack_i] = 0), stack[stack_i])) // 二叉樹的先序遍歷 // // 遞回版本 void preorder(const struct tree *t){ if(t == NULL) return; visit(t); preorder(t->left); preorder(t->right); } // 回圈版本 // 如何變成回圈呢，方法就是遞回怎么來，我們就怎么來， // 1. 呼叫visit，但是呼叫之后要恢復兩個函式呼叫，為了恢復現場，需要在堆疊空間中保存后續要做的事，我們這里顯然不需要保存cpu暫存器等，只需要保存t->left和t->right就可以了，由于是先呼叫t->left，后呼叫t->right，所以入堆疊就要反過來， //push(t->right); //push(t->left); //能不能直接push(t)呢，答案是不能，除非標記t已經訪問過了，否則就回圈訪問t了，但是標記t訪問過了還是要把t->right和t->left入堆疊，不如就直接來，更直接， // 2. t訪問完了，遞回程式就恢復現場，回傳到visit的下一個地址執行，恢復現場就對應我們的出堆疊，繼續執行同樣的preorder邏輯就相當于我們重復一次回圈， // 3. 遞回程式繼續這個程序，直到函式堆疊上的最底層，也就是最后一個函式呼叫回傳，對應我們的繼續這個程序，直到堆疊里面沒有資料了為止， // 代碼如下 void preorder_loop0(const struct tree *in) { const struct tree *t = in; if(t == NULL) return; do{ visit(t); push(t->right); push(t->left); }while((t = pop()) != NULL); } //這個程式是最原始的貼近遞回的版本，還可以繼續優化，visit(t)之后pop出來的一定是t->left，那么下次一定是visit(t->left)，往下遞推，每一次都是visit(t->left)，也就是說按照一直向左的方向遍歷就可以了，需要入堆疊的只是右子樹，但是右子樹誰先誰后呢，從遞回程式可以看出，所有的左子樹成員都在右子樹的前面遍歷，也就是說最接近樹根的大叉是優先級最低的，遠離樹根的在左子樹上的右子樹更優先，也就是說，入堆疊的順序和訪問的順序相同，即 // void preorder_loop1(const struct tree *in) { const struct tree *t = in; if(t == NULL) return; do{ while(t) { visit(t); push(t->right); t = t->left; } }while((t = pop()) != NULL); } // 將上面兩種版本對比，想象一下preorder_loop0的執行程序，也可以直接優化為preorder_loop1 //中序遍歷 // 遞回版本 void inorder(const struct tree *t){ if(t == NULL) return; inorder(t->left); visit(t); inorder(t->right); } // 第一步還是按照和遞回一一對應的方式來轉換成回圈，這個地方有點復雜，因為第一個函式不是visit，本身就是個遞回的，這時候的處理方式不唯一，可以直接把遞回版本函式中最上面的那個inorder展開，也可以按照通用的回圈中的邏輯來處理那個inorder，前者直接就是優化之后的了，另外由于inorder和visit是兩種操作，為了區分是哪一種操作，還需要在入堆疊的時候加標記等， void inorder_loop0(const struct tree *in) { int is_visit = 0; const struct tree *t = in; if(t == NULL) return; do{ if(is_visit) visit(t); else { push2(t->right, 0); push2(t, 1); push2(t->left, 0); } }while((t = pop2(is_visit)) != NULL); } // 簡化push(t->left); 同preorder的方法 void inorder_loop1(const struct tree *in) { int is_visit = 0; const struct tree *t = in; if(t == NULL) return; do{ if(is_visit) visit(t); else { while(t) { push2(t->right, 0); push2(t, 1); t = t->left; } } }while((t = pop2(is_visit)) != NULL); } // 繼續優化，每次pop出來的一定是先visit的，然后接著就是它的right，那么兩者可以合成一個整體，這樣也不用標記是否是is_visit了 void inorder_loop2(const struct tree *in) { const struct tree *t = in; if(t == NULL) return; while(t) { push(t); t = t->left; } while((t = pop()) != NULL) { visit(t); // pop -> t if(t->right) // pop -> t->right { t = t->right; while(t) { push(t); t = t->left; } } } } // 后續遍歷 // 遞回版本 void postorder(const struct tree *t){ if(t == NULL) return; postorder(t->left); postorder(t->right); visit(t); } // 和中序遍歷相同的方式，唯一一個區別就是 visit(t) 和postorder(t->right)的順序換了一下，也就是入堆疊的順序換了一下，代碼如下： void postorder_loop0(const struct tree *in) { int is_visit = 0; const struct tree *t = in; if(t == NULL) return; do{ if(is_visit) visit(t); else { push2(t, 1); push2(t->right, 0); push2(t->left, 0); } }while((t = pop2(is_visit)) != NULL); } // 前面已經用過這種思路，去掉push t->left(附帶的pop也一起去掉了) void postorder_loop1(const struct tree *in) { int is_visit = 0; const struct tree *t = in; if(t == NULL) return; do{ if(is_visit) visit(t); else { while(t) { push2(t, 1); push2(t->right, 0); t = t->left; } } }while((t = pop2(is_visit)) != NULL); } // t->right 先出堆疊，處理完整棵樹才能繼續處理t(即visit(t))，所以t和t->right不能當成一個整體來優化 // 但仍然可以繼續優化，t->right的處理程序是先push 它自己，也就是說visit(t)的時候上一次pop一定是 // t->right，并且pop -> t->right 然后pop -> t 的時候一定是訪問t的時候，這是后序遍歷的定義的必然 // 即 t->right == NULL 或last_pop/visit == t->right就是visit(t)的時刻，這樣可以去掉is_visit的標記 // 使用更簡單的push 和 pop void postorder_loop2(const struct tree *in) { const struct tree *t = in, *last_visit = NULL; if(t == NULL) return; while(t) { push(t); push(t->right); t = t->left; } while((t = pop()) != NULL) { if(t->right == NULL || last_visit == t->right) { visit(t); last_visit = t; } else { while(t) { push(t); push(t->right); t = t->left; } } } } int main(int argc, char *argv[]) { /* * * 4 * / \ * 2 6 * / \ / \ * 1 3 5 8 * / \ * 7 9 * * */ struct tree t[9] = { {1, NULL,NULL}, {2, &t[0],&t[2]}, {3, NULL,NULL}, {4, &t[1],&t[5]}, {5, NULL,NULL}, {6, &t[4],&t[7]}, {7, NULL,NULL}, {8, &t[6],&t[8]}, {9, NULL,NULL}, }; preorder(&t[3]); puts(""); assert(stack_i == 0); preorder_loop0(&t[3]); assert(stack_i == 0); puts(""); preorder_loop1(&t[3]); assert(stack_i == 0); puts(""); inorder(&t[3]); assert(stack_i == 0); puts(""); inorder_loop0(&t[3]); assert(stack_i == 0); puts(""); inorder_loop1(&t[3]); assert(stack_i == 0); puts(""); inorder_loop2(&t[3]); puts(""); postorder(&t[3]); puts(""); assert(stack_i == 0); postorder_loop0(&t[3]); assert(stack_i == 0); puts(""); postorder_loop1(&t[3]); assert(stack_i == 0); puts(""); postorder_loop2(&t[3]); assert(stack_i == 0); return 0; }
尾遞回和非尾遞回是否能轉換呢，對于Fibonacci數列這樣的特殊情況當然可以，但有些問題就是遞回模型，比如快速排序，所以是無法直接轉換的，如果非要轉換的話，也是可以的，借助額外實作的堆疊，因為回圈和尾遞回是等價的，回圈加額外的堆疊能實作的，尾遞回加額外的堆疊也能實作，但是這樣做是否有意義呢，人工精心優化的回圈/尾遞回程式和非尾遞回相比，有時候也許能獲得少量性能提升，但是代碼的可讀性卻很差，而非尾遞回程式卻是非常直觀，
補充一點，看編譯器是否進行了尾遞回優化，可以通過gdb或objdump看匯編，看尾遞回發生的時候后面是否有其他操作，或者是否還有遞回的呼叫，gcc O2一定會優化的， 如果通過試驗測驗，建議數字要足夠大，因為優化之后的程式可能占用堆疊空間很小，而行程的堆疊空間可能又很大，所以沒有進行尾遞回優化依然可能不會堆疊溢位，
總之，遞回是一種非常好的模型，堆疊空間一般可預測，尾遞回因為利用函式實作，區域變數隔離，也會增加安全性，但是記得開優化，盡量不用堆疊和回圈替代遞回，增加代碼可讀性，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/254662.html
標籤：C