有人说，回溯实际上是递归的展开，但实际上。两者的指导思想并不一致。
而回溯法则是一个人走迷宫的思维模拟——他只能寄希望于自己的记忆力，假如他没有办法在分岔口留下标记（电视里一演到什么迷宫寻宝，总有恶人去改好人的标记）。
想到这里忽然有点明白为什么都喜欢递归了，他能够满足人心最底层的虚荣——难道你不觉得使用递归就象那个分派士兵的将军吗？想想汉诺塔的解法，也有这个倾向，“你们把上面的N－1个拿走，我就能把下面的挪过去，然后你们在把那N－1个搬过来”。笑谈，切勿当真。
这两种方法的例程，我不给出了，网上很多。我只想对书上的递归解法发表点看法，因为书上的解法有偷梁换柱的嫌疑——迷宫的储存不是用的二维数组，居然直接用岔路口之间的连接表示的——简直是人为的降低了问题的难度。实际上，假如把迷宫抽象成（岔路口）点的连接，迷宫就变成了一个“图”，求解入口到出口的路线，完全可以用图的遍历算法来解决，只要从入口DFS到出口就可以了；然而，从二维数组表示的迷宫转化为图是个很复杂的过程。并且这种转化，实际上就是没走迷宫之前就知道了迷宫的结构，显然是不合理的。对此，我只能说这是为了递归而递归，然后还自己给自己开绿灯。
但迷宫并不是只能用上面的方法来走，前提是，迷宫只要走出去就可以了，不需要找出一条可能上的最短路线——确实，迷宫只是前进中的障碍，一旦走通了，没人走第二遍。下面的方法是一位游戏玩家提出来的，既不需要递归，也不需要栈往返溯——玩游戏还是有收获的。
另一种解法
请注重我在迷宫中用粗线描出的路线，实际上，在迷宫中，只要从入口始终沿着一边的墙走，就一定能走到出口，那位玩家称之为“靠一边走”——假如你不把迷宫的通路看成一条线，而是一个有面积的图形，很快你就知道为什么。编程实现起来也很简单。
更多内容请看C/C++技术专题 数据结构 数据结构教程专题，或 下面的程序在TC2中编译，不能在VC6中编译——为了动态的表现人的移动情况，使用了gotoxy()，VC6是没有这个函数的，而且堆砌迷宫的219号字符是不能在使用中文页码的操作系统的32位的console程序显示出来的。 #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,
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++技术专题 数据结构 数据结构教程专题，或 总结书上讲的基本上就这些了，要是细说起来，几天几夜也说不完。前面我并没有讲如何写递归算法，实际上给出的都是非递归的方法，我也觉得有点文不对题。
最后说说用汇编语言写递归函数。我的汇编水平并不高，不过我想说的是用汇编写递归函数，绝对不像《汇编与c解决递归问题之比较》http://www.csdn.net/develop/article/17/17597.shtm那篇文章说的，实际上比高级语言并不复杂，甚至在masm32v7中，和高级语言一样，因为那里面有一句很象代参函数调用的INVOKE eXPression [，arguments]。那位作者显然连教科书都没看全，因为在我们的讲8086汇编语言的书上就有一个阶乘的递归函数例程，假如他看过，就不会有那个结论了。
更多内容请看C/C++技术专题 数据结构 数据结构教程专题，或
