從漢諾塔問題理解迭代與遞歸

來自專欄自學編程之道

迭代與遞歸兩種演算法之間的關係就像水蒸氣和液態水，二者本質相同，可以相互轉化（準確來說遞歸都可以轉化為迭代，而迭代不一定都能轉化為遞歸）。這篇文章將以經典的漢諾塔問題來深入了解迭代與遞歸之間的關係。

遞歸與迭代的區別與聯繫

遞歸簡單來講就是函數的自身調用：

要實現這個過程，圖中的「函數」要包含循環的條件和調用自身的語句，通過這個不斷自身調用的過程把問題不斷化簡，最終達到解決的目的。

迭代簡單來講就是循環：

類比於我們循環輸出某一個字元數組時的情景：從字元數組中不斷取出字元，再將字元輸出。迭代的循環過程則是從棧（或者隊列）中不斷取出要操作的元素，進行操作，與普通循環過程不同的是在不斷取出元素的同時也會向棧中放入元素，從而實現迭代過程。

因而迭代的要點有：迭代的初始條件，迭代過程中迭代元素生成，迭代結束條件判斷。

下面分析漢諾塔問題

漢諾塔：漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

把這個問題抽象出來就是要我們把n個盤子從一根柱子上移動到另一個柱子上，期間可以藉助第三根柱子。n個盤子好像無從下手，我們來看三個盤子，假設要將三個盤子從A柱移動到B柱（藉助C柱），那麼就很簡單了，我們只需這樣移動：A->B A->C B->C A->B C->A C->B A->B。四個盤子呢？因為我們知道如何將三個盤子從一個柱子移動到另一個柱子，於是我們可以將四個盤子看作兩個盤子，最底下的看作一個（記作盤1），上面三個整體作為一個（記作盤2），假設要將四個盤子從A柱移動到B柱，那麼我們只需這樣移動：將盤1移動到C柱，盤2移動到B柱，最後將盤1移動到B柱。這樣我們又知道了如何移動四個盤子，移動五個盤子的方法就變成了將最底下的盤子看作盤1，上面的四個盤子看作盤2。最終我們就可以知道n個盤子如何移動了，這就是遞歸思想。

遞歸實現漢諾塔問題

//move方法，實現將n個盤子從moveFrom柱藉助swap柱移動到moveTo柱void move(int n, char moveFrom, char moveTo, char swap){ if (n == 1) { printf("%c->%c ", moveFrom, moveTo); return; } move(n - 1, moveFrom, swap, moveTo); move(1, moveFrom, moveTo, swap); move(n - 1, swap, moveTo, moveFrom);}int main(){ int n = 7; //調用move函數 move(n, A, B, C); system("pause"); return 0;}

迭代實現漢諾塔問題

迭代所需要的元素、棧以及操作棧的方法pop（向棧中放入元素）和push（從棧頂取出元素）

typedef struct record //用於記錄遞歸環境，放入棧中{ int n; char moveFrom; char moveTo; char swap; struct record *next;} record;typedef struct stack //定義一個棧{ record * records; int num;} stack;void push(record *record, stack *stack) //向棧內放置元素{ stack->num++; record->next = stack->records; stack->records = record;}record * pop(stack *stack) //從棧頂彈出元素{ record *record; stack->num--; record = stack->records; stack->records = stack->records->next; return record;}

實現迭代的方法：

//move方法，實現將n個盤子從moveFrom柱藉助swap柱移動到moveTo柱void move(int n, char moveFrom, char moveTo, char swap){ stack stack = { NULL, 0 }; record *record1, *p_record; //初始化棧 record1 = (record *)malloc(sizeof(record)); record1->n = n, record1->moveFrom = moveFrom, record1->moveTo = moveTo; record1->swap = swap; push(record1, &stack); //迭代開始 while (stack.num != 0) { //從棧中取出元素，並進行相應操作 p_record = pop(&stack); if (p_record->n == 1) { printf("%c->%c ", p_record->moveFrom, p_record->moveTo); free(p_record); continue; } //記錄遞歸環境，並放入棧中 record *record2 = (record *)malloc(sizeof(record)); record *record3 = (record *)malloc(sizeof(record)); record *record4 = (record *)malloc(sizeof(record)); record2->n = p_record->n - 1, record2->moveFrom = p_record->moveFrom, record2->moveTo = p_record->swap, record2->swap = p_record->moveTo; record3->n = 1, record3->moveFrom = p_record->moveFrom, record3->moveTo = p_record->moveTo, record3->swap = p_record->swap; record4->n = p_record->n - 1, record4->moveFrom = p_record->swap, record4->moveTo = p_record->moveTo, record4->swap = p_record->moveFrom; push(record4, &stack); push(record3, &stack); push(record2, &stack); //不要忘記釋放內存 free(p_record); }}int main(){ int n = 7; //調用move方法 move(n, A, B, C); system("pause"); return 0;}

兩種方法的運行結果比較

用Visual Studio調試的結果，在移動同樣多的盤子情況下，兩種方法消耗的內存相差不大，但時間有較大差別，使用迭代的方法花費的時間是遞歸方法的近十倍。原因有以下幾點：

1. 迭代過程中要反覆地動態創建變數，這也是時間開銷差距的主要原因
2. 遞歸過程由於編譯過程對遞歸變數和遞歸函數有很好的優化處理，因而效率較高

那麼什麼時候該用遞歸什麼時候該用迭代呢？我給大家的建議是，能用遞歸實現的就盡量用遞歸實現，不能用遞歸實現的那就只能用迭代了。

遞歸與迭代相互轉化

前面已經提到過遞歸都可以轉化為迭代，而迭代不一定都能轉化為遞歸，那麼二者之間具體的轉化關係是什麼，什麼情況下二者可以相互轉化，什麼情況下又不可以呢？

這個問題與函數調用的方式有關，函數調用其他函數的時候，函數本身的運行狀態被系統放入棧中，待它調用的函數執行完後才會繼續執行，換句話說，系統用棧來保存函數，而棧是後入先出的數據結構，這就導致遞歸順序的局限性。

舉個例子，如果要實現廣度優先搜索，那麼我們只能用迭代的方法，而且迭代用到的不再是棧，而是隊列（先進先出）。

總結一下就是遞歸都能轉化為迭代，而只有使用棧的迭代才能轉化為遞歸。