搜索
例题计算n的阶乘#includestdio.hintfactorial(intn){intresult;if(n0)//判断例外{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#includestdio.h/*定义获取单词数量的函数*/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岁），再往回推。#includestdio.h/**请使用递归函数完成本题*小编已将正确代码放在左侧任务的“不知道怎么办”里*小编希望各位童鞋独立完成哦~*///定义一个函数，传送人员序号进去，返回该序号员工的年龄。intgetAge(numPeople){//定义返回的年龄intage;//如果是第1个人的时候，年龄为10岁if(numPeople==1)age=10;//这是回推墙，也就是结束递归的条件。else//还没接触到回推墙，就自我调用，谓之递归。age=getAge(numPeople-1)+2;//年龄等于上一个人的年龄加2returnage;}intmain(){printf(第5个人的年龄是%d岁,getAge(5));return0;}例题猴子第一天摘下N个桃子，当时就吃了一半，还不过瘾，就又多吃了一个。第二天又将剩下的桃子吃掉一半，又多吃了一个。以后每天都吃前一天剩下的一半零一个。到第10天在想吃的时候就剩一个桃子了,问第一天共摘下来多少个桃子？并反向打印每天所剩桃子数。#includestdio.h//定义一个函数，输入第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(n0)//阶乘intrecursive(inti){intsum=0;if(0==i)return(1);elsesum=i*recursive(i-1);returnsum;}（2）河内塔问题//河内塔voidhanoi(intn,intp1,intp2,intp3){if(1==n)cout盘子从p1移到p3endl;else{hanoi(n-1,p1,p3,p2);cout盘子从p1移到p3endl;hanoi(n-1,p2,p1,p3);}}（3）全排列从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。如1,2,3三个元素的全排列为：1,2,31,3,22,1,32,3,13,1,23,2,1//全排列inlinevoidSwap(int&a,int&b){inttemp=a;a=b;b=temp;}voidPerm(intlist[],intk,intm){if(k==m-1){for(inti=0;im;i++){printf(%d,list[i]);}printf(n);}else{for(inti=k;im;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(n1)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;ia.length-1;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为求多个数的和的递归函数.代码如下：#includeiostreamusingnamespacestd;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;coutF(a,s,e)endl;return0;}4.求数组元素最大值手动求最大值的过程是什么，遍历+比较，过程如下：例如，求3,2,6,7,2,4的最大值：先设置最大值max=-999999，然后将max和数组元素逐个(遍历)比较如果a[i]max，则更新max的值为a[i]，否则max不变，继续向后遍历，直到遍历结束.max3，则max=3max2，max=3不变max6，则max=6max7，则max=7max2，max=7不变max4，max=7不变遍历结束，max=7为最大值.和求和类似，递归的公式如下：其中max为求两个数的较大值函数，F为求多个数的最大值的递归函数.代码如下：#includeiostreamusingnamespacestd;#definemax(a,b)(ab?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;coutF(a,s,e)endl;return0;}之所以，说上面的几个例子是【简单例子】，是因为上述所有的递归都属于【单向递归】.单向递归，递归的路径就是一个方向，所以思路相对比较容易想到.-