递归算法的例题及解析,递归算法举例

求汉诺塔C递归算法详细解答

Hanoi塔问题, 算法分析如下，设A上有n个盘子。

如果n=1，则将圆盘从A直接移动到C。

如果n=2，则：

（1）将A上的n-1（等于1）个圆盘移到B上；

（2）再将A上的一个圆盘移到C上；

（3）最后将B上的n-1（等于1）个圆盘移到C上。

如果n=3，则：

A）将A上的n-1（等于2，令其为n`）个圆盘移到B（借助于C），步骤如下：

（1）将A上的n`-1（等于1）个圆盘移到C上。

（2）将A上的一个圆盘移到B。

（3）将C上的n`-1（等于1）个圆盘移到B。

B）将A上的一个圆盘移到C。

C）将B上的n-1（等于2，令其为n`）个圆盘移到C（借助A），步骤如下：

（1）将B上的n`-1（等于1）个圆盘移到A。

（2）将B上的一个盘子移到C。

（3）将A上的n`-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。

从上面分析可以看出，当n大于等于2时， 移动的过程可分解为三个步骤：第一步 把A上的n-1个圆盘移到B上；第二步 把A上的一个圆盘移到C上；第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。 当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上，这里的n`=n-1。

Hanoi塔问题中函数调用时系统所做工作

一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完成3件事：

①将所有的实参、返回地址等信息传递给被调用函数保存。

②为被调用函数的局部变量分配存储区；

③将控制转移到被调用函数的入口。

从被调用函数返回调用函数前，系统也应完成3件事：

①保存被调用函数的结果；

②释放被调用函数的数据区；

③依照被调用函数保存的返回地址将控制转移到调用函数。

当有多个函数构成嵌套调用时，按照“后调用先返回”的原则（LIFO），上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，每当从一个函数退出时，就释放其存储区，因此当前运行函数的数据区必在栈顶。堆栈特点：LIFO，除非转移或中断，堆栈内容的存或取表现出线性表列的性质。正是如此，程序不要求跟踪当前进入堆栈的真实单元，而只要用一个具有自动递增或自动递减功能的堆栈计数器，便可正确指出最后一次信息在堆栈中存放的地址。

一个递归函数的运行过程类型于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入下一层，即i＋1层。反之，退出第i层递归应返回至上一层，即i－1层。为了保证递归函数正确执行，系统需设立一个“递归工作栈”，作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有实参、所有局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。

P.S.代码如您写的。

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,ij)

则称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其中一种语言来写）!

我用C#来写（注意，更多的请直接到我的个人博客，点击， ，收看） 【例1】有甲、乙、丙、丁四人，从甲开始到丁，一个比一个大1岁，已知丁10岁，问甲几岁？【分析】这是递归法的一道非常典型的题目——因为我们可以很显然知道：假设要计算甲的年龄，那么必须直到乙的年龄；同样，算乙的必须直到丙的，算丙的必须知道丁的，因为丁已知，自然可以往前推算了。现在假设有一个数学模型（函数）可以计算出他们各自的年龄（方便期间我们给他们编号——甲＝1，乙＝2，丙＝3，丁＝4），那么存在这一个F(X)函数，X表示某人的编号，其规律如下：F(1)=F(2)+1F(2)=F(3)+1F(3)=F(4)+1F(4)=10显然，直到X=4的时候是一个终止值，其余情况下都是返回F(X’)，F(X’’)……F(X’’……’)，且前者总是比后至大1，这也符合了X’和X总是呈现一定函数关系（设想一下，如果不是等差和等比，又怎么可能在一个递归函数中进行计算？要知道，函数本身就是一个公式表示，既然是公式，那么一定是一种函数关系Y=F(X)），此处显然X和X’的关系是X=X’+1。根据规律式，我们可以写出该递归函数：int AgeCal(int id)

{

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(int[]numbers)

{

if(numbers.Length==2)

{

return (numbers[0]numbers[1]?numbers[0]:numbers[1]);

}

else

{

int[]tempnumbers=new int[numbers.Length-1];

for(int i=0;inumbers.Length-1;++i)

{

tempnumbers[i]=numbers[i];

}

return (Max(tempnumbers)numbers[numbers.Length-1]? Max(tempnumbers): numbers[numbers.Length-1]

}

}

面试题递归算法

我来这么解释把 当你激活了程序Foo(30) 。那么根据程序 i=30;即不=0 也不=2,那么他就走 Foo(i -1) + Foo(i - 2);

那i-1 跟 i-2 是什么东西的呢，那就是F(29)+F(28);

同理F(29) 怎么拆呢？。。依次照F(30)的方式下去。当遇到F(2)的时候，程序判断 返回一个1，那么最后由N多的1组织一步步返回，最后得到F(30)

下面是一个简单的递归小题目，本人对递归不太懂，求详解下面的递归程序，递归的详细算法步骤。

#include "stdio.h"

void fun (int x) //x=6

{

if(x/20) //第一次，因为x=6，所以x/20成立，进行fun(x/2);x=x/2=6/2=3;进行相同步骤

fun(x/2);

printf("%d",x);当x/20不成立时，不断调用，反向输出刚刚出现的x的值

}

void main()

{

fun(6);//从这里开始调用fun这个函数，将6给x

printf("\n");

}