关于递归，我语言表达能力有限无法组织好所以摘了篇文章。。。
在实际编程中,有许多定义或者问题本身就具有递归性质。所以我们顺其自然就想到用递归来解决。这样不仅代码少,而且结构清晰。但是问题是我们应该怎样设计递归呢?这确实一个问题,由于许多问题并不是很明显的表现出递归的关系,所有很大一部分需要我们进行推导,从而得出递归关系,有了递归关系,编写代码就相对的比较简单了。
首先,我们了解递归算法的特点,所谓的递归,就是把一个大型的复杂的问题层层的转化为一个与原问题相似的较少规模的问题,在逐步求解小问题后,再返回得到较大问题的解。由于递归只需要少量的步骤就可描述解题过程中所需要的多次重复计算,所以大大的减少了代码量。
递归算法设计的关键在于,找出递归方程和递归终止条件(边界条件)。递归关系就是使问题向边界条件转化的过程。因此,递归关系必须能使问题越来越简单,规模越小。
因此,递归算法设计,通常有以下3个步骤:
(1)分析问题,得出递归关系。
(2)设置边界条件,控制递归。
(3)设计函数,确定参数。
好了，说了,这么多，我相信大家迫不及待要大显身手一番了吧,现在我们就通过一个具体的问题来前面阐述递归算法的设计过程。
问题 整数划分的问题
对于一个整数n的划分,就是把n表示成一系列的正整数的和的表达市。
注意划分与次序无关。
例如,6可以可以划分为
6;
5+1;
4+2,4+1+1
3+3,3+2+1,3+1+1+1
2+2+2,2+2+1+1,2+1+1+1+1
1+1+1+1+1+1
现在问题是,给一个n求他的所以划分。
这个问题初看,很难找出大规模问题与小规模问题之间的关系,我们注意了,对于上面的第一行,所以加数不超过6,第2行,所以加数不超过 5,。。。。。。。。。。。。。。。。。第6行所以加数不超过1。因此,我们可以定义一个q(n,m)的函数,表示 n所以加数不超过m的划分数目。
所以 n的划分总数目可以表示为q(n,n)。那我们怎样才能把找出q(n,n)的递归关系呢?
很显然,我们可以立即得到以下关系,
(1)q(n,n)=q(n,n-1)+1;
所以问题规模变小,但是我们很不能根据这个关系转化为更小的问题,所以我们主要考虑这种情况:q(n,m),怎样把这中情况分解呢。
我们尝试的把q(n,m)变为q(n,m-1);我们惊奇的发现,只要把q(n,m-1)加上包含加数m的项就等于q(n,n)。即q(n, m)=q(n,m-1)+包含m加数的表达式数。例如m=4,我们可以把q(n,4)=q(n,3)+2(包含4加数的表达使有两个:4+2,4+1+ 1)。
而我们发现,包含4的表达可以转化为q(n-m,n-m)(想想?);所以的递归关系式就出来了。
(2)q(n,m)=q(n,m-1)+q(n-m,n-m);
接下来就是找边界条件了,我们知道当n=1时,q(n,n)=1。
当m =1时,q(n,m)=1;有了边界条件,我们递归基本上完成了,编写代码如下:
#include
int f(int n,int m)
{
if(n==1||m==1)
{
return 1;
}
else if(n==m)
{
return f(n,n-1)+1;
}
else if(nm)
{
return f(n,m-1)+f(n-m,m);
}
}
main()
{
int n,sum;
scanf("%d",&n);
sum=f(n,n);
printf("%d\n",sum);
}
以上摘自搏客圆，作者sherlockhua。
递归 递归是一种重要的编程技术。该方法用于让一个函数从其内部调用其自身。一个示例就是计算阶乘。0 的阶乘被特别地定义为 1。 更大数的阶乘是通过计算 1 * 2 * 。。。来求得的，每次增加 1，直至达到要计算其阶乘的那个数。 下面的段落是用文字定义的计算阶乘的一个函数。
“如果这个数小于零，则拒绝接收。如果不是一个整数，则将其向下舍入为相邻的整数。如果这个数为 0，则其阶乘为 1。如果这个数大于 0，则将其与相邻较小的数的阶乘相乘。” 要计算任何大于 0 的数的阶乘，至少需要计算一个其他数的阶乘。用来实现这个功能的函数就是已经位于其中的函数；该函数在执行当前的这个数之前，必须调用它本身来计算相邻的较小数的阶乘。
这就是一个递归示例。 递归和迭代（循环）是密切相关的 — 能用递归处理的算法也都可以采用迭代，反之亦然。确定的算法通常可以用几种方法实现，您只需选择最自然贴切的方法，或者您觉得用起来最轻松的一种即可。 显然，这样有可能会出现问题。可以很容易地创建一个递归函数，但该函数不能得到一个确定的结果，并且不能达到一个终点。
这样的递归将导致计算机执行一个“无限”循环。下面就是一个示例：在计算阶乘的文字描述中遗漏了第一条规则（对负数的处理） ，并试图计算任何负数的阶乘。这将导致失败，因为按顺序计算 -24 的阶乘时，首先不得不计算 -25 的阶乘；然而这样又不得不计算 -26 的阶乘；如此继续。
很明显，这样永远也不会到达一个终止点。 因此在设计递归函数时应特别仔细。如果怀疑其中存在着无限递归的可能，则可以让该函数记录它调用自身的次数。如果该函数调用自身的次数太多，即使您已决定了它应调用多少次，就自动退出。 下面仍然是阶乘函数，这次是用 JScript 代码编写的。
// 计算阶乘的函数。如果传递了 // 无效的数值（例如小于零）， // 将返回 -1，表明发生了错误。若数值有效， // 把数值转换为最相近的整数，并 // 返回阶乘。 function factorial(aNumber) { aNumber = Math。
floor(aNumber); // 如果这个数不是一个整数，则向下舍入。 if (aNumber < 0) { // 如果这个数小于 0，拒绝接收。 return -1; } if (aNumber == 0) { // 如果为 0，则其阶乘为 1。
return 1; } else return (aNumber * factorial(aNumber - 1)); // 否则，递归直至完成。 } 。
答：public class BB { static int sum; void Sum50(int a) { int i=a; sum=sum+i; if(i>0...详情>>
