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

遞迴與迭代的區別與聯絡

遞迴簡單來講就是函式的自身呼叫：

要實現這個過程，圖中的“函式”要包含迴圈的條件和呼叫自身的語句，透過這個不斷自身呼叫的過程把問題不斷化簡，最終達到解決的目的。

迭代簡單來講就是迴圈：

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

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

下面分析漢諾塔問題

漢諾塔：漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著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\t”， 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\t”， 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除錯的結果，在移動同樣多的盤子情況下，兩種方法消耗的記憶體相差不大，但時間有較大差別，使用迭代的方法花費的時間是遞迴方法的近十倍。原因有以下幾點：

迭代過程中要反覆地動態建立變數，這也是時間開銷差距的主要原因

遞迴過程由於編譯過程對遞迴變數和遞迴函式有很好的最佳化處理，因而效率較高

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

遞迴與迭代相互轉化

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

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

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

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