首页 > C/C++语言 > C/C++数据结构 > 数据结构学习(C++)——递归
2006
09-01

数据结构学习(C++)——递归

 

递归法和回溯法


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


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


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


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


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


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


另一种解法


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


下面的程序在TC2中编译,不能在VC6中编译——为了动态的表现人的移动情况,使用了gotoxy()VC6是没有这个函数的,而且堆砌迷宫的219号字符是不能在使用中文页码的操作系统的32位的console程序显示出来的。如果要在VC6中实现gotoxy()的功能还得用API,为了一个简单的程序没有必要,所以,就用TC2写了,突然换到C语言还有点不适应。


#include <stdio.h>


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] =


{


       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汇编语言的书上就有一个阶乘的递归函数例程,如果他看过,就不会有那个结论了。


留下一个回复