递归法的解决方法

‘壹’ 什么是递归算法

递归算法就是一个函数通过不断对自己的调用而求得最终结果的一种思维巧妙但是开销很大的算法。
比如：
汉诺塔的递归算法：
void move(char x,char y){
printf("%c-->%c\n",x,y);
}

void hanoi(int n,char one,char two,char three){
/*将n个盘从one座借助two座，移到three座*/
if(n==1) move(one,three);
else{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}

main(){
int n;
printf("input the number of diskes:");
scanf("%d",&n);
printf("The step to moving %3d diskes:\n",n);
hanoi(n,'A','B','C');
}
我说下递归的理解方法
首先：对于递归这一类函数，你不要纠结于他是干什么的，只要知道他的一个模糊功能是什么就行，等于把他想象成一个能实现某项功能的黑盒子，而不去管它的内部操作先，好，我们来看下汉诺塔是怎么样解决的
首先按我上面说的把递归函数想象成某个功能的黑盒子，void hanoi(int n,char one,char two,char three); 这个递归函数的功能是：能将n个由小到大放置的小长方形从one 位置，经过two位置 移动到three位置。那么你的主程序要解决的问题是要将m个的"汉诺块"由A借助B移动到C，根据我们上面说的汉诺塔的功能，我相信傻子也知道在主函数中写道：hanoi(m,A,B,C)就能实现将m个块由A借助B码放到C，对吧？所以，mian函数里面有hanoi(m,'A','C','B');这个调用。
接下来我们看看要实现hannoi的这个功能，hannoi函数应该干些什么？
在hannoi函数里有这么三行
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
同样以黑盒子的思想看待他，要想把n个块由A经过B搬到C去，是不是可以分为上面三步呢？
这三部是：第一步将除了最后最长的那一块以外的n-1块由one位置经由three搬到two 也就是从A由C搬到B 然后把最下面最长那一块用move函数把他从A直接搬到C 完事后 第三步再次将刚刚的n-1块借助hannoi函数的功能从B由A搬回到C 这样的三步实习了n块由A经过B到C这样一个功能，同样你不用纠结于hanoi函数到底如何实现这个功能的，只要知道他有这么一个神奇的功能就行
最后：递归都有收尾的时候对吧，收尾就是当只有一块的时候汉诺塔怎么个玩法呢？很简单吧，直接把那一块有Amove到C我们就完成了，所以hanoni这个函数最后还要加上 if(n==1)move(one,three);（当只有一块时，直接有Amove到C位置就行）这么一个条件就能实现hanoin函数n>=1时将n个块由A经由B搬到C的完整功能了。
递归这个复杂的思想就是这样简单解决的，呵呵 不知道你看懂没？纯手打，希望能帮你理解递归
总结起来就是不要管递归的具体实现细节步骤，只要知道他的功能是什么，然后利用他自己的功能通过调用他自己去解决自己的功能（好绕口啊，日）最后加上一个极限情况的条件即可，比如上面说的1个的情况。

‘贰’ C语言递归算法

本人学c++，c的语法已经淡忘了，但是递归不管什么语言都是一个原理
其实简单一点来说就像数学里面的数列的通项公式：
例如一个数列是2，4，6，8，10......
很容易就可以得到通项公式是a[n]=2*n n是大于0的整数
你肯定学过这个数列的另外一种表示方式就是： a[1]=2, a[n]=a[n-1]+2 n是大于1的整数
其实这就是一个递归的形式，只要你知道初始项的值，未知项和前几项之间的关系就可以知道整个数列。
程序例子：比如你要得到第x项的值
普通循环：
for(int i=1; i<=n; i++)
if (i == x)
cout << 2*i; /*cout 相当于 c里面的printf,就是输出.*/
递归：
int a(int x) {
if (x = 1)
return 2; /* 第一项那肯定是2了，这个也是递归的终止条件！ */
else return a(x-1)+2; /* 函数自身调用自身是递归的一个特色 */
比如x=4,那么用数学表示就是a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2
其实递归方法最接近自然，也是最好思考的一个方法，难点就是把对象建模成递归形式，但是好多问题本身就是以递归形式出现的。
普通递归就是数据结构上的堆栈，先进后出。
例如上面x=4,把a(4)放入栈底，然后放入a(3),然后a(2),a(1),a(1)的值已知，出栈，a(1)=2,a(2)出栈a(2)=a(1)+2=2+2=4,a(3)出栈a(3)=a(2)+2=(a(1)+2)+2=6,a(4)出栈a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2=8
再比如楼上的阶乘例子，当n=0 或 1时,0!=1,1!=1,这个是阶乘的初始值，也是递归的终止条件。然后我们知道n!=n*(n-1)!,当n>1时,这样我们又有了递归形式，又可以以递归算法设计程序了。（楼上已给出谭老的程序，我就不写了）。
我给出一种优化的递归算法---尾递归。
从我给出的第一算法可以看出，先进栈再出栈，递归的效率是很低的。速度上完全比不上迭代（循环）。但是尾递归引入了一个新的函数参数，用这个新的函数参数来记录中间值.
普通递归阶乘fac(x),就1个x而已，尾递归用2个参数fac(x,y),y存放阶乘值。
所以谭老的程序就变成
// zysable's tail recursive algorithm of factorial.
int fac(int x, int y) {
if (x == 1)
return y;
else return fac(x-1, y*x);}
int ff(int x) {
if (x == 0)
return 1;
else return fac(x,1);}
对于这个程序我们先看函数ff，函数ff其实是对fac的一个封装函数，纯粹是为了输入方便设计的，通过调用ff(x)来调用fac(x,1),这里常数1就是当x=1的时候阶乘值了，我通过走一遍当x=3时的值即为3!来说明一下。
首先ff(3),x!=0,执行fac(3,1).第一次调用fac，x=3,y=1,x!=1,调用fac(x-1,y*x),新的x=2,y=3*1=3,这里可以看到，y已经累计了一次阶乘值了，然后x还是!=1,继续第三次调用fac(x-1,y*x),新的x=1,y=2*3=6,然后x=1了，返回y的值是6，也就是3！.你会发现这个递归更类似于迭代了。事实上我们用了y记录了普通递归时候，出栈的乘积，所以减少了出栈后的步骤，而且现在世界上很多程序员都在倡议用尾递归取消循环，因为有些在很多解释器上尾递归比迭代稍微效率一点.
基本所有普通递归的问题都可以用尾递归来解决。
一个问题以递归来解决重要的是你能抽象出问题的递归公式，只要递归公式有了，你就可以放心大胆的在程序中使用，另外一个重点就是递归的终止条件；
其实这个终止条件也是包含在递归公式里面的，就是初始值的定义。英文叫define initial value. 用普通递归的时候不要刻意让自己去人工追踪程序，查看运行过程，有些时候你会发现你越看越不明白，只要递归公式转化成程序语言正确了，结果必然是正确的。学递归的初学者总是想用追踪程序运行来让自己来了解递归，结果越弄越糊涂。
如果想很清楚的了解递归，有种计算机语言叫scheme,完全递归的语言，因为没有循环语句和赋值语句。但是国内人知道的很少，大部分知道是的lisp。
好了，就给你说到这里了，希望你能学好递归。

PS:递归不要滥用，否则程序极其无效率，要用也用尾递归。by 一名在美国的中国程序员zysable。

‘叁’ 请问运用递归关系的三个条件是什么

1、可以把要解决的问题转化为一个新问题，而这个新的题的解决方法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减。

2、可以应用这个转化过程使问题得到解决。

3、必定要有一个明确的结束递归的条件。

例如：

public class X {

public static void main(String[] args){

int x =new X(). x(100);

System.out.println(x);

}

//1～n 的累加递归

public int x(int n){

return n>1?n+x(--n):n;

}

}

(3)递归法的解决方法扩展阅读

设(a0，a1，...，ar，...)是一个序列，把该序列中的ar和它前面的几个ai(0≤i<r)关联起来的方程一个递归关系。如关系式:ar=3ar-1(r≥1)和错排数，Dn=(n-1)(Dn-1+Dn-2) (n=3，4，...)，都是递归关系。

有时也称递归关系式为差分方程。为了能从递归关系式计算出序列的每一项，必须知道序列开始的一个或几个数，称这样的数为初始条件或初始值。

在许多情况下，得到递归关系式本身就是朝解决一个计数问题迈了一大步。即使不能从这个递归关系式很快地解出它的一般表达式，这也是相当不错的了。这是因为采取逐步计算的方法可以得到序列各项的值。有些例子说明，没有递归关系，计算的可能性根本就不存在。

‘肆’ java中递归算法是什么怎么算的

一、递归算法基本思路：

Java递归算法是基于Java语言实现的递归算法。递归算法是一种直接或者间接调用自身函数或者方法的算法。递归算法实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法表示问题的解。递归往往能给我们带来非常简洁非常直观的代码形式，从而使我们的编码大大简化，然而递归的思维确实跟我们的常规思维相逆的，通常都是从上而下的思维问题，而递归趋势从下往上的进行思维。

二、递归算法解决问题的特点：

【1】递归就是方法里调用自身。

【2】在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

【3】递归算法代码显得很简洁，但递归算法解题的运行效率较低。所以不提倡用递归设计程序。

【4】在递归调用的过程中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

【5】在做递归算法的时候，一定把握出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口就是一个条件，当满足了这个条件的时候我们就不再递归了。

三、代码示例：

publicclassFactorial{

//thisisarecursivefunction

intfact(intn){

if(n==1)return1;

returnfact(n-1)*n;

}}

publicclassTestFactorial{publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

Factorialfactorial=newFactorial();

System.out.println("factorial(5)="+factorial.fact(5));

}
}

代码执行流程图如下：

此程序中n=5就是程序的出口。

‘伍’ 请教高人 递归算法编写思路技巧

一个子程序（过程或函数）的定义中又直接或间接地调用该子程序本身，称为递归。递归是一种非常有用的程序设计方法。用递归算法编写的程序结构清晰，具有很好的可读性。递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
利用递归算法解题，首先要对问题的以下三个方面进行分析：
一、决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。
二、问题的边界条件及边界值。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。
三、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。把这些步骤或等式确定下来。
把以上三个方面分析好之后，就可以在子程序中定义递归调用。其一般格式为：
if 边界条件 1 成立 then
赋予边界值 1
【 elseif 边界条件 2 成立 then
赋予边界值 2
┇ 】
else
调用解决问题的通式
endif
例 1 ： 计算勒让德多项式的值

x 、 n 由键盘输入。
分析： 当 n ＝ 0 或 n ＝ 1 时，多项式的值都可以直接求出来，只是当 n ＞ 1 时，才使问题变得复杂，决定问题复杂程度的参数是 n 。根据题目提供的已知条件，我们也很容易发现，问题的边界条件及边界值有两个，分别是：当 n ＝ 0 时 P n (x) ＝ 1 和当 n ＝ 1 时 P n (x) ＝ x 。解决问题的通式是：
P n (x) ＝ ((2n － 1)P n － 1 (x) － (n － 1)P n － 2 (x)) ／ n 。
接下来按照上面介绍的一般格式定义递归子程序。
function Pnx(n as integer)
if n ＝ 0 then
Pnx ＝ 1
elseif n ＝ 1 then
Pnx ＝ x
else
Pnx ＝ ((2*n － 1)*Pnx(n － 1) － (n － 1)*Pnx(n － 2)) ／ n
endif
end function
例 2 ： Hanoi 塔问题：传说印度教的主神梵天创造世界时，在印度北部佛教圣地贝拿勒斯圣庙里，安放了一块黄铜板，板上插着三根宝石针，在其中一根宝石针上，自下而上地放着由大到小的 64 个金盘。这就是所谓的梵塔（ Hanoi ），如图。梵天要求僧侣们坚持不渝地按下面的规则把 64 个盘子移到另一根针上：

(1) 一次只能移一个盘子；
(2) 盘子只许在三根针上存放；
(3) 永远不许大盘压小盘。
梵天宣称，当把他创造世界之时所安放的 64 个盘子全部移到另一根针上时，世界将在一声霹雳声中毁灭。那时，他的虔诚的信徒都可以升天。
要求设计一个程序输出盘子的移动过程。
分析： 为了使问题更具有普遍性，设共有 n 个金盘，并且将金盘由小到大依次编号为 1 ， 2 ，…， n 。要把放在 s(source) 针上的 n 个金盘移到目的针 o(objective) 上，当只有一个金盘，即 n ＝ 1 时，问题是比较简单的，只要将编号为 1 的金盘从 s 针上直接移至 o 针上即可。可定义过程 move(s,1,o) 来实现。只是当 n>1 时，才使问题变得复杂。决定问题规模的参数是金盘的个数 n ；问题的边界条件及边界值是：当 n ＝ 1 时， move(s,1,o) 。
当金盘不止一个时，可以把最上面的 n － 1 个金盘看作一个整体。这样 n 个金盘就分成了两个部分：上面 n － 1 个金盘和最下面的编号为 n 的金盘。移动金盘的问题就可以分成下面三个子问题（三个步骤）：
(1) 借助 o 针，将 n － 1 个金盘（依照上述法则）从 s 针移至 i(indirect) 针上；
(2) 将编号为 n 的金盘直接从 s 针移至 o 针上；
(3) 借助 s 针，将 i 针上的 n － 1 个金盘（依照上述法则）移至 o 针上。如图

其中第二步只移动一个金盘，很容易解决。第一、第三步虽然不能直接解决，但我们已经把移动 n 个金盘的问题变成了移动 n － 1 个金盘的问题，问题的规模变小了。如果再把第一、第三步分别分成类似的三个子问题，移动 n － 1 个金盘的问题还可以变成移动 n － 2 个金盘的问题，同样可变成移动 n － 3 ，…， 1 个金盘的问题，从而将整个问题加以解决。
这三个步骤就是解决问题的通式，可以以过程的形式把它们定义下来：
hanoi(n － 1,s,o,i)
move(s,n,o)
hanoi(n － 1,i,s,o)
参考程序如下：
declare sub hanoi(n,s,i,o)
declare sub move(s,n,o)
input "How many disks?",n
s ＝ 1
i ＝ 2
o ＝ 3
call hanoi(n,s,i,o)
end
sub hanoi(n,s,i,o)
rem 递归子程序
if n ＝ 1 then
call move(s,1,o)
else
call hanoi(n － 1,s,o,i)
call move(s,n,o)
call hanoi(n － 1,i,s,o)
endif
end sub
sub move(s,n,o)
print "move disk";n;
print "from";s;"to";o
end sub

‘陆’ 递归主方法

递归的主要方法是什么？

一、递归算法
递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。
二、递归程序
在支持自调的编程语言中，递归可以通过简单的函数调用来完成，如计算阶乘的程序在数学上可以定义为：

这一程序在Scheme语言中可以写作：
1
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))
不动点组合子
即使一个编程语言不支持自调用，如果在这语言中函数是第一类对象（即可以在运行期创建并作为变量处理），递归可以通过不动点组合子（英语：Fixed-point combinator）来产生。以下Scheme程序没有用到自调用，但是利用了一个叫做Z 算子（英语：Z combinator）的不动点组合子，因此同样能达到递归的目的。
1
(define Z (lambda (f) ((lambda (recur) (f (lambda arg (apply (recur recur) arg)))) (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))(define fact (Z (lambda (f) (lambda (n) (if (<= n 0) 1 (* n (f (- n 1))))))))
这一程序思路是，既然在这里函数不能调用其自身，我们可以用 Z 组合子应用(application)这个函数后得到的函数再应用需计算的参数。
尾部递归
尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言（如Scheme中）可以被优化为循环指令。 因此，在这些语言中尾部递归不会占用调用堆栈空间。以下Scheme程序同样计算一个数字的阶乘，但是使用尾部递归：
1
(define (factorial n) (define (iter proct counter) (if (> counter n) proct (iter (* counter proct) (+ counter 1)))) (iter 1 1))
三、能够解决的问题
数据的定义是按递归定义的。如Fibonacci函数。
问题解法按递归算法实现。如Hanoi问题。
数据的结构形式是按递归定义的。如二叉树、广义表等。
四、递归数据
数据类型可以通过递归来进行定义，比如一个简单的递归定义为自然数的定义：“一个自然数或等于0，或等于另一个自然数加上1”。Haskell中可以定义链表为：
1
data ListOfStrings = EmptyList | Cons String ListOfStrings
这一定义相当于宣告“一个链表或是空串行，或是一个链表之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。

‘柒’ 递归算法

递归算法
递归算法流程
递归过程一般通过函数或子过程来实现。递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。
递归算法的特点
递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。 递归算法解决问题的特点： (1) 递归就是在过程或函数里调用自身。 (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 (3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
递归算法要求
递归算法所体现的“重复”一般有三个要求： 一是每次调用在规模上都有所缩小(通常是减半)； 二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)； 三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
举例
描述：把一个整数按n(2<=n<=20)进制表示出来，并保存在给定字符串中。比如121用二进制表示得到结果为：“1111001”。 参数说明：s: 保存转换后得到的结果。 n: 待转换的整数。 b: n进制（2<=n<=20） void numbconv(char *s, int n, int b) { int len; if(n == 0) { strcpy(s, ""); return; } /* figure out first n-1 digits */ numbconv(s, n/b, b); /* add last digit */ len = strlen(s); s[len] = ""[n%b]; s[len+1] = '\0'; } void main(void) { char s[20]; int i, base; FILE *fin, *fout; fin = fopen("palsquare.in", "r"); fout = fopen("palsquare.out", "w"); assert(fin != NULL && fout != NULL); fscanf(fin, "%d", &base); /*PLS set START and END*/ for(i=START; i <= END; i++) { numbconv(s, i*i, base); fprintf(fout, "%s\n", s); } exit(0); }
编辑本段递归算法简析（PASCAL语言）
递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写 程序能是程序变得简洁和清晰.
一 递归的概念
1.概念 一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数). 如: procere a; begin . . . a; . . . end; 这种方式是直接调用. 又如: procere c(形参);forward; procere b; 局部说明 begin . . c(实参); . . end; procere c; 局部说明； begin . . b; . . end; 这种方式是间接调用. 例1计算n!可用递归公式如下: fac:=n*fac(n-1) {当n>0时} fac(n)={ fac:=1; { 当n=0时} 可编写程序如下: program facn; var n:integer; function fac(n:integer):real; begin if n=0 then fac:=1 else fac:=n*fac(n-1); end; begin write('n=');readln(n); writeln(n,'!=',fac(n):0:0); end. 例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法. 设n阶台阶的走法数为f(n) 显然有 n=1 f(n)={ f(n-1)+f(n-2) n>2 可编程序如下： program louti; var n:integer; function f(x:integer):integer; begin if x=1 then f:=1 else if x=2 then f:=2 else f:=f(x-1)+f(x-2); end; begin write('n=');read(n); writeln('f(',n,')=',f(n)) end.
二 如何设计递归算法
1.确定递归公式 2.确定边界(终了)条件
三 典型例题
例3 汉诺塔问题 如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子 从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上 不能出现大盘压小盘.找出移动次数最小的方案. 程序如下: program hanoi; var n:integer; procere move(n,a,b,c:integer); begin if n=1 then writeln(a,'->',c) else begin move(n-1,a,c,b); writeln(a,'--->',c); move(n-1,b,a,c); end; end; begin write('Enter n='); read(n); move(n,1,2,3); end. 例4 快速排序 快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束. 程序如下: program kspv; const n=7; type arr=array[1..n] of integer; var a:arr; i:integer; procere quicksort(var b:arr; s,t:integer); var i,j,x,t1:integer; begin i:=s;j:=t;x:=b ; repeat while (b[j]>=x) and (j>i) do j:=j-1; if j>i then begin t1:=b; b:=b[j];b[j]:=t1;end; while (b<=x) and (i<j) do i:=i+1; if i<j then begin t1:=b[j];b[j]:=b;b:=t1; end until i=j; b:=x; i:=i+1;j:=j-1; if s<j then quicksort(b,s,j); if i<t then quicksort(b,i,t); end; begin write('input data:'); for i:=1 to n do read(a); writeln; quicksort(a,1,n); write('output data:'); for i:=1 to n do write(a:6); writeln; end.
编辑本段{递归的一般模式}
procere aaa(k:integer); begin if k=1 then (边界条件及必要操作) else begin aaa(k-1); (重复的操作); end; end;
开放分类：
编程，计算机，算法

引自：http://ke..com/view/1733593.htm

‘捌’ 一个递归算法必须包括什么

一个递归算法必须包括终止条件和递归部分。

递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

能够解决的问题：

数据的定义是按递归定义的。如Fibonacci函数。

问题解法按递归算法实现。如Hanoi问题。

数据的结构形式是按递归定义的。如二叉树、广义表等。