递归题目.docx
- 文档编号:10049560
- 上传时间:2023-05-23
- 格式:DOCX
- 页数:14
- 大小:55.62KB
递归题目.docx
《递归题目.docx》由会员分享,可在线阅读,更多相关《递归题目.docx(14页珍藏版)》请在冰点文库上搜索。
递归题目
例题
计算n的阶乘
#include
intfactorial(intn)
{
intresult;
if(n<0) //判断例外
{
printf("输入错误!
\n");
return0;
}elseif(n==0||n==1)
{
result=1; //回推墙
}
else
{
result=factorial(n-1)*n; //递推关系,这个数与上一个数之间的关系。
}
returnresult;
}
intmain(){
intn=5; //输入数字5,计算5的阶乘
printf("%d的阶乘=%d",n,factorial(n));
return0;
}
程序在计算5的阶乘的时候,先执行递推,当n=1或者n=0的时候返回1,再回推将计算并返回。
由此可以看出递归函数必须有结束条件。
递归函数特点:
1. 每一级函数调用时都有自己的变量,但是函数代码并不会得到复制,如计算5的阶乘时每递推一次变量都不同;
2. 每次调用都会有一次返回,如计算5的阶乘时每递推一次都返回进行下一次;
3. 递归函数中,位于递归调用前的语句和各级被调用函数具有相同的执行顺序;
4. 递归函数中,位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反;
5. 递归函数中必须有终止语句。
一句话总结递归:
自我调用且有完成状态。
例题
小明为了学好英语,需要每天记单词,第一天记1个,第二天记2个依次类推,请用代码完成,算出小明第10天开始的时候会了多少个单词?
分析:
回推墙是“第一天记1个”
递推关系是“第n天记的单词=第n-1天记的单词数量+n"
#include
/*定义获取单词数量的函数*/
intgetWordNumber(n)
{
if(n==1)
{
return1; //回推墙
}
else{
returngetWordNumber(n-1)+n; //递推关系
}
}
intmain()
{
intnum=getWordNumber(10); //获取会了的单词数量
printf("小明第10天记了:
%d个单词。
\n",num);
return0;
}
例题
有5个人坐在一起,问第5个人多少岁?
他说比第4个人大2岁。
问第4个人岁数,他说比第3个人大2岁。
问第3个人,又说比第2人大两岁。
问第2个人,说比第1个人大两岁。
最后问第1个人,他说是10岁。
请问第5个人多大?
程序分析:
利用递归的方法,递归分为回推和递推两个阶段。
要想知道第5个人岁数,需知道第4人的岁数,依次类推,推到第1人(10岁),再往回推。
#include
/*
*请使用递归函数完成本题
*小编已将正确代码放在左侧任务的“不知道怎么办”里
*小编希望各位童鞋独立完成哦~
*/
//定义一个函数,传送人员序号进去,返回该序号员工的年龄。
intgetAge(numPeople)
{
//定义返回的年龄
intage;
//如果是第1个人的时候,年龄为10岁
if(numPeople==1)
age=10; //这是回推墙,也就是结束递归的条件。
else
//还没接触到回推墙,就自我调用,谓之递归。
age=getAge(numPeople-1)+2; //年龄等于上一个人的年龄加2
returnage;
}
intmain()
{
printf("第5个人的年龄是%d岁",getAge(5));
return0;
}
例题
猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又多吃了一个。
第二天又将剩下的桃子吃掉一半,又多吃了一个。
以后每天都吃前一天剩下的一半零一个。
到第10天在想吃的时候就剩一个桃子了,问第一天共摘下来多少个桃子?
并反向打印每天所剩桃子数。
#include
//定义一个函数,输入第n天,返回该天剩下的桃子数
intgetPeachNumber(n)
{
intnum; //定义所剩桃子数
if(n==10)
{
num=1; //递归结束条件,即回推墙
returnnum;
}
else
{
num=(getPeachNumber(n+1)+1)*2; //递推关系
printf("第%d天所剩桃子%d个\n",n,num);//天数,所剩桃子个数
}
returnnum;
}
intmain()
{
intnum=getPeachNumber
(1);
printf("猴子第一天摘了:
%d个桃子。
\n",num);
return0;
}
递归(recursion):
程序调用自身的编程技巧。
递归满足2个条件:
1)有反复执行的过程(调用自身)
2)有跳出反复执行过程的条件(递归出口)
递归例子:
(1)阶乘
n!
=n*(n-1)*(n-2)*...*1(n>0)
//阶乘
intrecursive(inti)
{
intsum=0;
if(0==i)
return
(1);
else
sum=i*recursive(i-1);
returnsum;
}
(2)河内塔问题
//河内塔
voidhanoi(intn,intp1,intp2,intp3)
{
if(1==n)
cout<<"盘子从"< else { hanoi(n-1,p1,p3,p2); cout<<"盘子从"< hanoi(n-1,p2,p1,p3); } } (3)全排列 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。 当m=n时所有的排列情况叫全排列。 如1,2,3三个元素的全排列为: 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1 //全排列 inlinevoidSwap(int&a,int&b) { inttemp=a; a=b; b=temp; } voidPerm(intlist[],intk,intm) { if(k==m-1) { for(inti=0;i { printf("%d",list[i]); } printf("n"); } else { for(inti=k;i { Swap(list[k],list[i]); Perm(list,k+1,m); Swap(list[k],list[i]); } } } (4)斐波那契数列 斐波纳契数列,又称黄金分割数列,指的是这样一个数列: 1、1、2、3、5、8、13、21、…… 这个数列从第三项开始,每一项都等于前两项之和。 有趣的兔子问题: 一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。 如果所有兔子都不死,那么一年以后可以繁殖多少对兔子? 分析如下: 第一个月小兔子没有繁殖能力,所以还是一对; 两个月后,生下一对小兔子,总数共有两对; 三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,总数共是三对; …… 依次类推可以列出下表: //斐波那契 longFib(intn) { if(n==0) return0; if(n==1) return1; if(n>1) returnFib(n-1)+Fib(n-2); } (4)判定一系列字符串中是否有相同的内容 publicclassT{ publicstaticvoidmain(String[]args){ String[]a={"a1","a2","a3","b3","c","b","33","33"}; booleanb=newT().fun(0,a); System.out.println(b); } publicbooleanfun(intn,String[]a){ booleanb=false; if(n==a.length){ b=true; }else{ for(inti=n;i System.out.println(n+""+(i+1)); if(a[n].equals(a[i+1])){ returnfalse; } } n++; fun(n,a); } returnb; } } 1.Fibonacci数 我们直到Fibonacci数的递推公式为: F(0)=F (1)=1,F(n)=F(n-1)+F(n-2)n>=2; 这个明显地给出了递归边界n=0或1的时候F(n)的值,和递归逻辑F(n)=F(n-1)+F(n-2),即递推公式.所以这个递归函数不难书写 intF(intn)//函数返回一个数对应的Fibonacci数 2.阶乘 阶乘的递归公式为: 3.数组求和 给一个数组a[]: a[0],a[1],...,a[n-1]如何用递归的方式求和? 仍然是两个问题: 递归边界和递归公式. 递归边界是什么? 一时不容易想到,但是我们想到了求和,多个数的求和过程是什么,x,y,z,w手动求和的过程是什么? 步骤如下: x+y=a,任务变为a,z,w求和 a+z=b,任务变为b,w求和 b+w=c得出答案 思考一下,【得出答案】这一步为什么就可以得出答案呢? (废话? )是因为,一个数不用相加就能得出答案. 所以,递归的边界就是只有一个数. 所以,递归边界有了,那么递归公式呢? 其实手动计算过程中,隐含了递归公式: 其中+为求两个数的和,F为求多个数的和的递归函数.代码如下: #include usingnamespacestd; intF(inta[],intstart,intend) { if(start==end)//递归边界 returna[start]; returna[start]+F(a,start+1,end);//递归公式 } intmain() { inta[]={1,2,3,4,5}; ints=0,e=4; cout< return0; } 4.求数组元素最大值 手动求最大值的过程是什么,遍历+比较,过程如下: 例如,求3,2,6,7,2,4的最大值: 先设置最大值max=-999999,然后将max和数组元素逐个(遍历)比较如果a[i]>max,则更新max的值为a[i],否则max不变,继续向后遍历,直到遍历结束. max<3,则max=3 max>2,max=3不变 max<6,则max=6 max<7,则max=7 max>2,max=7不变 max>4,max=7不变 遍历结束,max=7为最大值. 和求和类似,递归的公式如下: 其中max为求两个数的较大值函数,F为求多个数的最大值的递归函数.代码如下: #include usingnamespacestd; #definemax(a,b)(a>b? a: b) intF(inta[],ints,inte) { if(s==e) returna[s]; elseif(s+1==e)//递归边界 returnmax(a[s],a[e]); returnmax(a[s],F(a,s+1,e));//递归公式! ! ! } intmain() { inta[]={5,1,4,6,2}; ints=0,e=4; cout< return0; } 之所以,说上面的几个例子是【简单例子】,是因为上述所有的递归都属于【单向递归】.单向递归,递归的路径就是一个方向,所以思路相对比较容易想到. -
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 递归 题目
![提示](https://static.bingdoc.com/images/bang_tan.gif)