遞歸法和回溯法
有人說，回溯實際上是遞歸的展開，但實際上。兩者的指導思想並不一致。
![]()
![]()
![]()
![]()
<!-- frame contents -->
<!-- /frame contents -->
![]()
![]()
![]()
![]()
打個比方吧，遞歸法好比是一個軍隊要通過一個迷宮，到了第一個分岔口，有3條路，將軍命令3個小隊分別去探哪條路能到出口，3個小隊沿著3條路分別前進，各自到達了路上的下一個分岔口，於是小隊長再分派人手各自去探路——只要人手足夠（對照而言，就是計算機的堆棧足夠），最後必將有人找到出口，從這人開始只要層層上報直屬領導，最後，將軍將得到一條通路。所不同的是，計算機的遞歸法是把這個並行過程串行化了。
而回溯法則是一個人走迷宮的思維模擬——他只能寄希望於自己的記憶力，假如他沒有辦法在分岔口留下標記（電視裡一演到什麼迷宮尋寶，總有惡人去改好人的標記）。
想到這裡忽然有點明白為什麼都喜歡遞歸了，他能夠滿足人心最底層的虛榮——難道你不覺得使用遞歸就象那個分派士兵的將軍嗎？想想漢諾塔的解法，也有這個傾向，“你們把上面的N－1個拿走，我就能把下面的挪過去，然後你們在把那N－1個搬過來”。笑談，切勿當真。
這兩種方法的例程，我不給出了，網上很多。我只想對書上的遞歸解法發表點看法，因為書上的解法有偷梁換柱的嫌疑——迷宮的儲存不是用的二維數組，居然直接用岔路口之間的連接表示的——簡直是人為的降低了問題的難度。實際上，假如把迷宮抽象成（岔路口）點的連接，迷宮就變成了一個“圖”，求解入口到出口的路線，完全可以用圖的遍歷算法來解決，只要從入口DFS到出口就可以了；然而，從二維數組表示的迷宮轉化為圖是個很復雜的過程。並且這種轉化，實際上就是沒走迷宮之前就知道了迷宮的結構，顯然是不合理的。對此，我只能說這是為了遞歸而遞歸，然後還自己給自己開綠燈。
但迷宮並不是只能用上面的方法來走，前提是，迷宮只要走出去就可以了，不需要找出一條可能上的最短路線——確實，迷宮只是前進中的障礙，一旦走通了，沒人走第二遍。下面的方法是一位游戲玩家提出來的，既不需要遞歸，也不需要棧往返溯——玩游戲還是有收獲的。
另一種解法
請注重我在迷宮中用粗線描出的路線，實際上，在迷宮中，只要從入口始終沿著一邊的牆走，就一定能走到出口，那位玩家稱之為“靠一邊走”——假如你不把迷宮的通路看成一條線，而是一個有面積的圖形，很快你就知道為什麼。編程實現起來也很簡單。
更多內容請看C/C++技術專題 數據結構 數據結構教程專題，或
下面的程序在TC2中編譯，不能在VC6中編譯——為了動態的表現人的移動情況，使用了gotoxy()，VC6是沒有這個函數的，而且堆砌迷宮的219號字符是不能在使用中文頁碼的操作系統的32位的console程序顯示出來的。
![]()
![]()
![]()
![]()
<!-- frame contents -->
<!-- /frame contents -->
![]()
![]()
![]()
![]()
假如要在VC6中實現gotoxy()的功能還得用API，為了一個簡單的程序沒有必要，所以，就用TC2寫了，忽然換到C語言還有點不適應。
#include
typedef strUCt hero {int x,y,face;} HERO;
void set_hero(HERO* h,int x,int y,int face){h->x=x;h->y=y;h->face=face;}
void go(HERO* h){if(h->face%2) h->x+=2-h->face;else h->y+=h->face-1;}
void goleft(HERO* h){if(h->face%2) h->y+=h->face-2;else h->x+=h->face-1;}
void turnleft(HERO* h){h->face=(h->face+3)%4;}
void turnright(HERO* h){h->face=(h->face+1)%4;}
void print_hero(HERO* h, int b)
{
gotoxy(h->x + 1, h->y + 1);
if (b)
{
switch (h->face)
{
case 0: printf("%c", 24); break;
case 1: printf("%c", 16); break;
case 2: printf("%c", 25); break;
case 3: printf("%c", 27); break;
default: break;
}
}
else printf(" ");
}
int maze[10][10] =
{
更多內容請看C/C++技術專題 數據結構 數據結構教程專題，或
0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
1, 0, 1, 1, 0, 1, 1, 1, 1, 0,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 1, 1, 0, 1, 1, 1,
0, 0, 1, 0, 1, 1, 0, 0, 0, 1,
1, 0, 1, 0, 1, 1, 0, 1, 0, 1,
![]()
![]()
![]()
![]()
<!-- frame contents -->
<!-- /frame contents -->
![]()
![]()
![]()
![]()
0, 0, 1, 0, 1, 1, 0, 1, 0, 1,
0, 1, 1, 0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 1, 0, 1, 1, 0, 1,
0, 1, 1, 1, 1, 0, 0, 0, 0, 0
};
void print_maze()
{
int i, j;
for (i = 0; i < 10; i++)
{
for (j = 0; j < 10; j++)
{
if (maze[i][j]) printf("%c", 219);
else printf(" ");
}
printf("
");
}
}
int gomaze(HERO* h)
{
HERO t = *h; int i;
for (i = 0; i < 2; t = *h)
{
print_hero(h, 1); sleep(1); go(&t);
if (t.x >= 0 && t.x < 10 && t.y >= 0 && t.y < 10 && !maze[t.y][t.x])
{
print_hero(h, 0); go(h);/*前方可走則向前走*/
if (h->x == 9 && h->y == 9) return 1; goleft(&t);
if (h->x == 0 && h->y == 0) i++;
if (t.x >= 0 && t.x < 10 && t.y >= 0 && t.y < 10 && !maze[t.y][t.x]) turnleft(h);/*左方無牆向左轉*/
}
else turnright(h);/*前方不可走向右轉*/
}
return 0;
}
main()
{
HERO Tom;/*有個英雄叫Tom*/
set_hero(&Tom, 0, 0, 0);/*放在(0,0)面朝北*/
clrscr();
print_maze();
gomaze(&Tom);/*Tom走迷宮*/
}
更多內容請看C/C++技術專題 數據結構 數據結構教程專題，或
總結
書上講的基本上就這些了，要是細說起來，幾天幾夜也說不完。前面我並沒有講如何寫遞歸算法，實際上給出的都是非遞歸的方法，我也覺得有點文不對題。
![]()
![]()
![]()
![]()
<!-- frame contents -->
<!-- /frame contents -->
![]()
![]()
![]()
![]()
我的目的是使大家明白，能寫出什麼算法，主要看你解決問題的指導思想，換而言之，就是對問題的熟悉程度。所以初學者現在就去追求“漂亮”的遞歸算法，是不現實的，結果往往就是削足適履，搞的一團糟——有位仁兄寫了個騎馬游世界的“遞歸”程序，在我機器上10分鐘沒反映。其實優秀的遞歸算法是在對問題有了清楚的熟悉後才會得出的。
最後說說用匯編語言寫遞歸函數。我的匯編水平並不高，不過我想說的是用匯編寫遞歸函數，絕對不像《匯編與c解決遞歸問題之比較》http://www.csdn.net/develop/article/17/17597.shtm那篇文章說的，實際上比高級語言並不復雜，甚至在masm32v7中，和高級語言一樣，因為那裡面有一句很象代參函數調用的INVOKE eXPression [，arguments]。那位作者顯然連教科書都沒看全，因為在我們的講8086匯編語言的書上就有一個階乘的遞歸函數例程，假如他看過，就不會有那個結論了。
更多內容請看C/C++技術專題 數據結構 數據結構教程專題，或
