递归法和回溯法


　　有人说，回溯实际上是递归的展开，但实际上。两者的指导思想并不一致。

　　打个比方吧，递归法好比是一个军队要通过一个迷宫，到了第一个分岔口，有3条路，将军命令3个小队分别去探哪条路能到出口，3个小队沿着3条路分别前进，各自到达了路上的下一个分岔口，于是小队长再分派人手各自去探路——只要人手足够（对照而言，就是计算机的堆栈足够），最后必将有人找到出口，从这人开始只要层层上报直属领导，最后，将军将得到一条通路。所不同的是，计算机的递归法是把这个并行过程串行化了。

　　而回溯法则是一个人走迷宫的思维模拟——他只能寄希望于自己的记忆力，如果他没有办法在分岔口留下标记（电视里一演到什么迷宫寻宝，总有恶人去改好人的标记）。

　　想到这里突然有点明白为什么都喜欢递归了，他能够满足人心最底层的虚荣——难道你不觉得使用递归就象那个分派士兵的将军吗？想想汉诺塔的解法，也有这个倾向，“你们把上面的N－1个拿走，我就能把下面的挪过去，然后你们在把那N－1个搬过来”。笑谈，切勿当真。

　　这两种方法的例程，我不给出了，网上很多。我只想对书上的递归解法发表点看法，因为书上的解法有偷梁换柱的嫌疑——迷宫的储存不是用的二维数组，居然直接用岔路口之间的连接表示的——简直是人为的降低了问题的难度。实际上，如果把迷宫抽象成（岔路口）点的连接，迷宫就变成了一个“图”，求解入口到出口的路线，完全可以用图的遍历算法来解决，只要从入口DFS到出口就可以了；然而，从二维数组表示的迷宫转化为图是个很复杂的过程。并且这种转化，实际上就是没走迷宫之前就知道了迷宫的结构，显然是不合理的。对此，我只能说这是为了递归而递归，然后还自己给自己开绿灯。

　　但迷宫并不是只能用上面的方法来走，前提是，迷宫只要走出去就可以了，不需要找出一条可能上的最短路线——确实，迷宫只是前进中的障碍，一旦走通了，没人走第二遍。下面的方法是一位游戏玩家提出来的，既不需要递归，也不需要栈来回溯——玩游戏还是有收获的。

　　另一种解法

　　请注意我在迷宫中用粗线描出的路线，实际上，在迷宫中，只要从入口始终沿着一边的墙走，就一定能走到出口，那位玩家称之为“靠一边走”——如果你不把迷宫的通路看成一条线，而是一个有面积的图形，很快你就知道为什么。编程实现起来也很简单。

　　下面的程序在TC2中编译，不能在VC6中编译——为了动态的表现人的移动情况，使用了gotoxy()，VC6是没有这个函数的，而且堆砌迷宫的219号字符是不能在使用中文页码的操作系统的32位的console程序显示出来的。如果要在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++] 的这些文章也感兴趣： C++学习:在C++中创建持久对象 C++基础:初始化类对象 C++数据结构学习:二叉树(4) 深入探讨C++中的引用 插入排序法 C++数据结构学习:递归(1) 二级C语言实例解答 C语言之声明的语法 C++数据结构学习:事件驱动模拟 PE文件格式详解(1)

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, 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[j]) printf("%c", 219);

　　else printf(" ");

　　}

　　printf("\n");

　　}

　　}

　　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走迷宫*/

　　}
　　总结

　　书上讲的基本上就这些了，要是细说起来，几天几夜也说不完。前面我并没有讲如何写递归算法，实际上给出的都是非递归的方法，我也觉得有点文不对题。我的目的是使大家明白，能写出什么算法，主要看你解决问题的指导思想，换而言之，就是对问题的认识程度。所以初学者现在就去追求“漂亮”的递归算法，是不现实的，结果往往就是削足适履，搞的一团糟——有位仁兄写了个骑马游世界的“递归”程序，在我机器上10分钟没反映。其实优秀的递归算法是在对问题有了清楚的认识后才会得出的。

　　最后说说用汇编语言写递归函数。我的汇编水平并不高，不过我想说的是用汇编写递归函数，绝对不像《汇编与c解决递归问题之比较》http://www.csdn.net/develop/article/17/17597.shtm那篇文章说的，实际上比高级语言并不复杂，甚至在masm32v7中，和高级语言一样，因为那里面有一句很象代参函数调用的INVOKE expression [，arguments]。那位作者显然连教科书都没看全，因为在我们的讲8086汇编语言的书上就有一个阶乘的递归函数例程，如果他看过，就不会有那个结论了。