递归算法经典实例（08《算法入门教程》递归算法之斐波那契数列）

本文目录

• 08《算法入门教程》递归算法之斐波那契数列
• 递归算法的经典例子
• 10道pascal的递归习题，简单一点啊
• 求经典的递归算法以及案例（可用C#、PHP、JAVA其中一种语言来写）!
• 递归知多少 递归过程演示，经典问题解决
• 1-100用c语言的递归法求和
• 用编写递归算法求1到n的和. 用编写递归算法求1到n的平方和 .用递归算法求一个数组中n个单元的和
• （1-2+3-4+5-6+7-8+9）用递归方法怎么写
• c语言,求递归算法的技巧最好有经典例子！

08《算法入门教程》递归算法之斐波那契数列

本节内容是递归算法系列之一：斐波那契数列递归求解，主要介绍了斐波那契数列的定义，然后用递归的实现思想分析了一下斐波那契数列，最后给出了基于 Java 代码应用递归思想实现斐波那契数列的代码实现及简单讲解。

斐波那契数列（Fibonacci sequence），也称之为黄金分割数列，由意大利数学家列昂纳多・斐波那契（Leonardo Fibonacci）提出。斐波那契数列指的是这样的一个数列：1、1、2、3、5、8、13、21、34、……，这个数列从第 3 项开始，每一项都等于前面两项之和。在数学上，斐波那契数列可以被递推的方法定义如下：

斐波那契数列是数学上面一个经典的例子，并且在日常生活中有很多应用，他还与黄金分割有着密不可分的联系，而且当 n 趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割值 0.618。

在这一节中，我们就需要利用递归的思想去求解斐波那契数列，当给出一个斐波那契中第几项的数字，然后求解出对应的斐波那契数值。在之前，我们已经定义了递归算法的相关概念，并且明确了需要应用递归时候的三要素：

接下来，我们将利用递归的知识来解决斐波那契数列问题，明确在斐波那契数列求解问题中的递归三要素分别是什么。

例如，当我们求解斐波那契数列中的 F (5) 时，按照定义，我们有：

在说明斐波那契数列的递归描述之后，我们看看如何用 Java 代码来实现对斐波那契数列的计算。

运行结果如下：

代码中的第 4 行至第 8 行分别调用斐波那契数列计算函数，计算出斐波那契数列中对应 n=1,2,3,4,5 时斐波那契数列的取值，进行结果比较，判断斐波那契数列程序实现是否正确。代码中的第 12 行至第 20 行是斐波那契数列应用递归方法进行斐波那契数列的计算，按照递归的三要素进行计算处理。

本节主要介绍了用递归思想求解斐波那契数列，在学完本节课程之后，我们了解到了什么是斐波那契数列，并且将递归算法在斐波那契数列中进行了实际应用，需要掌握斐波那契数列的递归求解方法，并自己可以实现相关的代码实现，并清楚里面的每一步逻辑。

递归算法的经典例子

具体如下。
递归阶乘n!=n*(n-1)*(n-2)*...*1(n》0)publicstaticIntegerrecursionMulity(Integern){if(n==1){汉诺塔问题publicstaticvoidhanio(intn，chara，charb，charc){判定一系列字符串中是否有相同的内容publicclassCrf。
递归算法（英语：recursionalgorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的。

10道pascal的递归习题，简单一点啊

1. 有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2个人，说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大。显然，这是一个递归问题。要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且每一个人的年龄都比其前1个人的年龄大2。
2.用递归方法求n！
3.用递归方法求斐波那契数列
4.有1*n的一个长方形，用一个1＊1、1＊2、1＊3的骨牌铺满方格。例如当n=3时为1＊3的方格。此时用1＊1，1＊2，1＊3的骨牌铺满方格，共有四种铺法。图4.4.3列出了四种铺法。
5.设s是一个具有n个元素的集合s={a1,a2,…an},现将s集合划分成k个满足下列条件的子集合s1,s2，s3。。。。；
1、si《》空；
2、si∩sj=空；
3、s1∪s2∪s3…. ∪sn=s (1《=i,j《=k,i《》j)
则称s1,s2…sn是集合s的一个划分，它相当于把集合s中的n个元素放入k个无标号的盒子中，使得没有一个盒子为空，试确定n个元素的集合放入k个无标号盒的划分数s(n,k)
6.设有一个背包，可以放入的重量为s。现有n件物品，重量分别为t1 , t2 , t3 … ti … tn ，ti (1≤ i≤n)，均为正整数。从n件物品中挑选若干件，使得放入背包的重量之和正好为s
【输入样例】 【输出样例】
the number of object:5 number:1 weight:1
total weight=10 number:3 weight: 2
1 6 2 7 5 number:4 weight:7
7.输出n个元素的无重复的全排列。N个元素有n！种不同排列
8.任何一个正整数都可以用2的幂次方表示.例如：137=2^7+2^3+2^0。同时约定次方用括号来表示，即a^b可表示为a(b)。由此可知，137可表示为：2(7)+2(3)+2(0)，进一步：7=2^2+2+2^0 (2^1用2表示)；3=2+2^0；所以最后137可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0)。又如：1315=2^10+2^8+2^5+2+1；所以1315最后可表示：2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
输入：正整数(n≤20000)
输出：符合约定的n的0，2表示(在表示中不能有空格)
9.。一个正整数的数字的乘积N的定义是：这个整数中非零数字的乘积。例如，整数999的数字乘积为9*9*9，即729。729的数字乘积为7*2*9，即126。126的数字乘积为1*2*6，即12。12的数字乘积为1*2，即2。一个正整数的数字乘积根N是这样得到的：反复取该整数的数字乘积，直到得到一位数字为止。例如，在上面的例子中数字的乘积根是2。
编写一个程序，输入一个正整数（长度不超过200位数字），输出计算其数字乘积根的每一步结果。
10.输入N个字符，然后以倒序输出（用递归实现）

求经典的递归算法以及案例（可用C#、PHP、JAVA其中一种语言来写）!

***隐藏网址***
{
if(id==4) return 10;
else
return (AgeCal(id+1)+1);
} 【例2】计算n！【分析】虽然这道题目不像例1一样清晰明了告诉你使用“递归”法反推，但是我们有这样一个常识——n！＝(n-1)!*n；(n-1)!=(n-2)!*(n-1)……n=0或1，返回1.显然n与n-1，n-2也是线性的递减数列（等差关系）。其规律如下：F(n)=F(n-1)*nF(n-1)=F(n-2)*(n-1)F(n-2)=F(n-3)*(n-2)……F(1)=1或者F(0)=1(防止别人直接输入0)编写其递归函数，如下：int Fac(int n)
{
if(n==1 || n==0)
{
return 1;
}
else
return Fac(n-1)*n;
} 【例3】求一组整数中的最大(小)值（整数是一个int数组，个数未知）。【分析】当数字只有两个的时候，我们可以使用》和《直接比较；但是当数字超过2个的时候（假设3个），那么我们可以使用一个预订的函数（比如Max(1,2)和3进行比较），由于1，2两个数比较的时候已经得到一个最大值，因此在回代到Max中又变成了两个数的比较。这样，我们可以发现一个规律：F(1,2,3,4……n)＝F(1,2,3,4……n-1)和n比较F(1,2,3,4……n-1)＝F(1,2,3,4……n-2)和n-1比较……F(1,2,3)=F(1,2)和3比较F(1,2)＝结果（并回代）相应的递归函数如下(C#)：Code
int Max(intnumbers)
{
if(numbers.Length==2)
{
return (numbers);
}
else
{
int;
for(int i=0;i《numbers.Length-1;++i)
{
tempnumbers;
}
return (Max(tempnumbers)》numbers
}
}

递归知多少 递归过程演示，经典问题解决

递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。
在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，……，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。
在编写递归函数时要注意，函数中的局部变量和参数只是局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。

1-100用c语言的递归法求和

1、首先本题的思路已经给出，要求用递归算法。

2、程序源代码如下：

#include《stdio.h》

int sum(int n);

int main()

{ 

int i=100;

printf("1~%d的和为：\n",i);

printf("%d\n",sum(100));

return 0;

}

//下面是一个递归求和函数

int sum(int n)

{

if (n==1) 

return 1;

else 

return n+sum(n-1);

}

3、程序的输出结果如下：

用编写递归算法求1到n的和. 用编写递归算法求1到n的平方和 .用递归算法求一个数组中n个单元的和

class Test
{
//1到n和的递归方法
public static int add(int max){
int sum=0;
if(max》0){
sum=max+add(max-1);
}
return sum;
}

//1到n平方和的递归方法
public static int squr(int max){
int sum=0;
if(max》0){
sum=max*max+squr(max-1);
}
return sum;
}
//数组元素之和
public static int arraySum(int array){
int sum=0;
for(int item:array){
sum+=item;
}
return sum;
}
//主函数
public static void main(String arg){
int n=5;
int a={1,2,3,5,7,10,12};
System.out.println("从1到"+n+"的和为："+Test.add(n));
System.out.println("从1到"+n+"的平方和为："+Test.squr(n));
System.out.println("数组元素之和为："+Test.arraySum(a));
}
}

（1-2+3-4+5-6+7-8+9）用递归方法怎么写

首先要理解递归本身其实是一项非常重要的算法技巧。
递归满足两个条件：
1，不断调用函数本身，也就是递归函数。
2，调用是有限的，也就是递归出口。
为了理解方便，下面是用一个最简单的例子：求n的阶乘。
n!(阶乘)定义：
n!数学意思为n!
=
n*(n-1)!
&
1!=1;
其实根据上面递归定义结合分析下就可以n阶乘的递归算法：
1,构造一个递归函数,不断乘以自身和使用自身减一后调用同样函数．
2,定义出口，当函数参数等于1时结束;
如果用iso
c++语言描述如下：
int
factorial(int
n){
if(
n
》
1){
return
n*factorial(n-1);//递归函数调用
}
else
if(n
==
1){
return
1;
//递归出口
}
else{
return
error;//报告输入错误
}
}
这里讨论主要的不是上面这个简单的例子，而是下面的一些改良．
因为递归设计大量的堆栈操作，所以一般都会考虑将递归转为非递归来执行．
这里用上面这个程序作一个分析例子来分析．
假设这里执行factorial(4)，那么程序会按照下面方式来执行：
(1)执行factorial(4)判断n
》
1执行factorial(3),并且将factorial(4)函数相关信息存入一个堆栈．
(2)执行factorial(3)判断n
》
1执行factorial(2),并且将factorial(3)函数相关信息存入一个堆栈．
(3)执行factorial(2)判断n
》
1执行factorial(1),并且将factorial(2)函数相关信息存入一个堆栈．
(4)执行factorial(1)判断n
==
1执行返回1;
(5)将factorial(2)函数从堆栈中弹出，执行2*1，并且返回2．
(6)将factorial(3)函数从堆栈中弹出，执行2*3，并且返回6．
(7)将factorial(4)函数从堆栈中弹出，执行6*4，并且返回24．
如下图所示：
factorial(4)
--》factorial(3);
--》factorial(2);
--》factorail(1);
《--factorail(1);
《--factorial(2);
《--factorial(3);
《--结果
可以看到中间涉及的堆栈操作是很大的开销，每次需要保存当前函数的所有信息．
为了避免这样情况，可以使用下面这几种方法来实现递归到非递归的转换．
(1)
循环方法
循环方法是所有递归到非递归的转换中最理想的方法，可以将开销减少到最小．
不过也是分析起来最复杂的，对于简单的递归可以用这样的方法来处理．
例如：factorial计算
这里回到n!(阶乘)定义上面来分析，这里将n!数学意思为n!
=
n*(n-1)!
&
1!=1;做一个扩展可以到到n!另外一个表示方法n!
=
n*(n-1)*(n-2)*....*1;
这样就可以很容易得到另外一个定义：
n!表示执行n次循环计算一个增量k，初始k=1和结果t=1;每次t乘以k++的值.
iso
c++实现代码如下：
factorial(int
n){
int
k
=
1
;//增量
int
t
=
1
;//临时结果
while(k!=n){
t*=k;
k++;
}
return
t;
}
这样可以避免递归带来的大量堆栈操作．
(2)
自定义堆栈
对于复杂逻辑的堆栈操作，需要借助外部堆栈来实现．
因为对于所有的递归操作最后分析出来都是形成的一颗树形结构．
下面是一个递归实现factorial的一个方法，虽然在这个程序中对比循环来相对复杂，不过对于一些不能分析出来循环的递归操作来说自定义堆栈的方法可以达到空间开销可控．
factorial(int
n){
stack
s;
int
t
=
1;//临时变量
s.push(n);
while(s.top()!=1)[
t
*=
s.top();
s.push(s.top()-1);
s.pop();
}
return
t;
}
除了上面这两种方法外，还可以使用一种迭代的方法实现递归到非递归的处理．

c语言,求递归算法的技巧最好有经典例子！

c语言中递归的最经典应用是求两个数的最小公约数，代码如下：
int MinDivisor( int m, int n)
{
if(m%n==0)
return n;
else
return MinDivisor(n, m%n);
}