大码女装的店名大全:如何建立递归的思想

很多初学者往往对递归迷惑不解，也在这上面花了不少的时间。其实教材上的例子很经典，只是它说的有一些唠叨了。初学者会看的头大的。编程是解决问题的，而现实中很多的问题都是比较简单的，没有象汉诺塔那么复杂。我们也不必追究递归到底是怎样实现的，我们只是要会用递归，会用递归来为我们解决一些问题，这就行了。

首先来看一个例子：

有一个Febonacci序列：

1,1,2,3,5,8,13,,21,34........

它的问题是：求这个序列中的第N个数。

由于它的函数原形是：f(n)=f(n-1)+f(n-2)

这用递归很容易就可以写出代码来，一点都不费事：

int Febc(int n) {

if(n<3) return (1);

else

return (Febc(n-1)+Febc(n-2));

}

噢~~~~~也许你会说递归真是太简单了，简直就是一个数学模型嘛，呵呵。

其实，递归函数的工作过程就是自己调用自己。有一些问题用递归就很容易解决，简单的你自己都会吃惊。

我们做事情，一般都是从头开始的，而递归却是从末尾开始的。比如上面的函数吧，当n>3时，它显然只能求助于n-1,n-2。而(n-1)>2,(n-2)>2时，它们就求助于：(n-1)-1,(n-1)-2;(n-2)-1,(n-2)-2;然后··············直到（n-k)<3,(n-k-1)<3时，函数Febc终于有了返回值1 了，它再从头开始计算，然后一直算到n 为止。

通过上面的例子，我们知道递归一定要有一个停止的条件，否则递归就不知道停止了。在上面的例子中， if(n<3) return (1); 就是停止的条件。

然而，使用递归的代价是十分巨大的：它会消耗大量的内存！！递归循环时它用的是堆栈，而堆栈的资源是十分有限的。上面的例子你只能用一个很小的n值。如果n=20，即Febc(20)的话，它将调用Febc(n)函数10000多次！！！而上面一个例子用循环也是十分容易写的：

/*using turboc2*/
int febc(int);
main()
{
int n;
scanf("%d",&n);
febc(n);
}

int febc(int n)
{
int a[3],i;
a[0]=a[1]=a[2]=1;
for(i=3;i<=n;i++)
a[i%3]=a[(i+1)%3]+a[(i+2)%3]; /*实现 Febc(i)=Febc(i-1)+Febc(i-2)*/
printf("\n%d\n",a[n%3]);
}

有兴趣者不妨输入一个较大的n值，然后比较比较这二个函数计算的速度。当然， 如果你使用的n太大的话，递归可能发生错误。如果死机了可别骂我哦~~~ 我已经提醒过你了 ：）

现在我们再来看看一个求从1 加到100的循环：

/*turboc2*/

main()

{ int i,n;

for(i=1;i<101;i++)

n+=i; }

这很简单没什么可说的。 但是，你能不能写出相应的递归函数呢？

如果一个结点A有左孩子B或右孩子C，则生成新的结点B或结点C；并保存和结点A 的父子关系；
如果B或C不存在，即你说的b=0，那就返回到结点A的父结点O；
假设A是O的左孩子，返回O后，继续处理O的右孩子；处理完了，再回到O的父结点；依此类推

如图，处理到H；H没有孩子，就要返回到D；D没有右孩子，继续返回到B；处理B的右孩子；

返回操作是由递归来完成的；
就像一个大人，让一个孩子去做一件事；做完了，必须告诉大人；然后，这个大人再让另一个孩子去做另一件事；而这需要第一个孩子告诉大人，他的完成情况大人知道以后，才会让另一个孩子去做另一件事。

简单的从1乘到n,复杂的象数列求和等,都需要用到递归.

象数列A(n)=A(n-1)*0.5+2,都有个通项公式和一个或几个初始项,可是这两个条件是没办法直接算出需要的某一项的值的,这时候只好从低项往高项算,一直算出结果...^_^
假设A(0)=5
int a0=5
int getResult(n){
if(!n)return a0;
return getResult(n-1)*0.5+2;
}
这个好好研究研究..然后做几个例子..实践一下..很快就可以搞清楚了..^_^

可以这样来理解递归：
1. 递归包含很多相同的步骤（或解决方法、途径）；
2. 相邻的递归步骤可以通过一个简单的操作来表示差异。

像汉诺塔的问题，就是将A的n个东西通过B挪到C
A -> B -> C
中间用到的步骤是这样的，先将A上的n-1个东西通过C挪到B，然后将A上的1个东西直接挪到C，然后再通过A将B上的n-1个东西挪到C。

看出门道了吗？
开始第一步后，后面的步骤其实是一摸一样的，直到挪完为止。
这就是递归，你只需要知道第一步是如何做的就可以了，以后的就是一样的步骤了。

明白道理跟应用总是有点差距