递归是程序设计的基础，而且是很有潜力可挖的设计模式之一
zouxiao
zouxiao
5
16
2004-11-01T05:42:00Z
2004-11-01T05:59:00Z
2
194
1110
sp
9
2
1363
9.2812
7.8 磅
0
2
递归是程序设计的基础，而且是很有潜力可挖的设计模式之一。递归有两种模式，一种是基于程序堆栈的内部递归，该方法用的最多，在小规模问题上最为方便，对于递归层次较深时，往往需要借助于外部的栈，但实现原理时一样的。
本文将介绍两个最基础的递归问题，该问题适合初学者，但解决该问题的方法要足够优雅，所以还是对能够熟练应用c＋＋的同仁们有一定参考价值的。
汉诺塔问题
谈到递归，就不能不谈一下汉诺塔，这是个十分著名而且也十分有意思的递归问题，要求是利用三个底座来移动一堆圆盘，要求将圆盘从A底座全部移到C底座，移动的顺序则必须是每次移动均保证每个底座上处于下部的盘子大于处于上部的盘子的面积。
大家可以从谭老师的c程序设计上得到一个官方解，但那绝对不是最简介和优雅的。下面我给出我的解法，算作抛砖，希望引出大家手里的玉。
#include <iostream.h>
#include <stdlib.h>
unsigned long time=0;
void hanor(int i,char a,char b,char c)
{
if(i>=2)
hanor(i-1,a,c,b);
cout<<i<<": "<<a<<"--->"<<c<<" "<<++time<<endl;
if(i>=2)
hanor(i-1,b,a,c);
}
int main()
{
hanor(16,'a','b','c');
system("PAUSE");
return 0;
}
八皇后问题
八皇后是另外一个递归经典问题，该问题要求在一个国际象棋盘上摆放8个皇后，皇后们均魅力四射，在米子型的格子上不允许其它皇后的存在，该问题较汉诺塔问题复杂一些，解答也较有趣一些。为了得到更加优雅和简介的解法，我再冒昧抛一块砖。
#include <iostream>
using namespace std;
#include <stdlib.h>
int queens[9];
bool is;
int total=0;
void run(int num)
{
for(int i=1;i<=8;i++)
{
queens[num]=i;
is=true;
for(int j=1;j<num;j++)
if(queens[j]==queens[num]||queens[j]+(num-j)==queens[num]||
queens[j]-(num-j)==queens[num])
{
is=false;
break;
}
if(is)
{
if(num==8)
{
for(int k=1;k<=8;k++)
cout<<queens[k]<<" ";
cout<<++total<<endl;
}
if(num<8)
run(num+1);
}
}
}
int main()
{
run(1);
system("PAUSE");
return 0;
}
故意不作注释了，希望如此短小的代码，能够有人愿意阅读分析。
设计递归程序是很有趣和有挑战性的，如何优雅简介，占用内存小，效率高，都是需要兼顾的，而且是构建许多实际应用的核心技术，大量的数据结构和算法，如BTree，桶、正则表达表达式匹配中，均大量使用了递归。希望该文能对大家有所借鉴。