资源描述：
《C语言：1.9递推与递归》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、主讲老师：欧阳坚欢迎您到（千锋学院）来学习!递推与递归内容摘要递推算法递归算法计算组合数汉诺塔问题快速排序问题递归思想递推与递归递推算法例题：古有善切饼者，名庖丙，庖丁之弟也。把一张大饼置于板上，不许离开，每一刀切下去都是一条直线。问切20刀最多能分成多少块？递推算法a(n)表示切n刀可以分成的块数a(1)=1+1=2//切第1刀多出1块a(2)=2+2=4//切第2刀多出2块a(3)=4+3=7//切第3刀多出3块a(4)=7+4=11//切第4刀多出4块归纳后得到规律：a(n)=a(n-1)+n//切第n刀多出n块
2、a(0)=1//不切时块数是1递推算法编写函数cutpie求解切n刀后得到的块数递推算法将复杂运算分解为若干重复的简单运算后一步骤建立于前一步骤之上计算每一步骤的方法相同从开始向后计算出结果使用循环结构，通过多次循环逐渐逼近结果a(i)a(i+1)=a(i)+i;a(0)a(1)a(n)……递推算法练习：递推数列：数列的每一项都可以通过前面若干项计算生成，可用递推公式定义练习：阶乘：1!,2!,3!,4!,……,(n-1)!,n!a(n)=n*a(n-1)//第n项通过第n-1项乘n得到a(1)=1练习：斐波那契数列：
3、1,1,2,3,5,8……a(n)=a(n-1)+a(n-2)a(0)=a(1)=1递推算法练习：老人死后留下一堆枣子，ABCDE五兄弟要来分。A先来了后把枣子平均分成5份后发现多出1个，就取走了其中一份和多出来的1个。B来后把剩下的枣子平均分成5份发现多出1个，就取走了其中一份和多出来的1个。CDE来了之后，分别使用同样的做法。编程求解最初至少有多少枣子。思路提示：BCDE看到的个数肯定应该是4的倍数每人都能把枣子分成5份多一个，说明他们看到的枣子数应该是5的倍数加1从小到大找到一个同时满足上面条件的数，即为E看到的
4、数目递推算法递归算法若一个过程直接或间接的调用自己，这个过程就是递归的过程一个比较复杂的问题，如果可以分解成为几个相对简单或规模较小且解法相同或类似的子问题时，只要解决了这些子问题，那么原来的问题也就可以解决了。这种策略称为分而治之法比如：求10！，只要求出子问题9!,乘上10就得到了10!;要求9!,只要求出了8!,乘上9就得到了9!……当分解出的子问题可以直接解决时，就停止分解。直接可以解决的子问题称为递归结束条件。比如：0!=1就是结束条件递归过程可以通过编写自我调用的递归函数来简单的解决递归算法切饼问题a(n)
5、=a(n-1)+n也可用以下递归方法求解n==0，返回1n>0,返回n-1的结果加上n递归算法参数：1计算cutpie(0)+1返回(2)参数：2计算cutpie(1)+2返回(4)参数：3计算cutpie(2)+3返回(7)参数：4计算cutpie(3)+4返回(11)main函数参数：0直接返回1返回(1)递归算法练习：使用递归方法求解斐波那契数列第n项a(n);练习：用递归方法求两个整数m和n的最大公约若m%n为零是，n是m和n的最大公约数若m%n不为零，n和m%n的最大公约数即为m和n的最大公约数练习：用递归的
6、方法求整数1…n的前n项和练习：让用户从键盘输入10个整数，逆序显示示例输入：12345910098示例输出：89010954321练习：从键盘输入底边长，在屏幕上打印倒三角形计算组合数编程实现组合计数C(10,3)C(m,n)=1;当m=nC(m,n)=m;当n=1C(m,n)=C(m-1,n)+C(m-1,n-1)思路提示m个球取出来的n个，包含两种情况：n在其中和n不在其中编程实现使用递归思想编写递归函数intcmn(intm,intn)计算组合数汉诺塔问题据说在古代印度bramah神庙中，有个和尚整天把3根柱子
7、上的金盘倒来倒去。初始在柱子A上有64个盘子串在一起，每一个盘子都比它下面的盘子小，可以在ABC三个柱子之间互相移动，最终要全部移动到柱子C上。移动规则如下：每次只允许移动一个，且较大的盘子永远不能放在较小的盘子上。如果每秒移动一个的话，移完需要5800亿年。若初始时盘子数是n,编程求出移动的过程盘子从小到大（从上到下）编号依次为1,2……n-1,n汉诺塔问题假如n=1，直接移动到C假如n=2，则需要先把1号盘移到B上，再把2号盘移动到C上，最后把1号盘移动到C上。(1)(2)(3)汉诺塔问题假如初始时有n个盘，把1到
8、n-1看作一个整体第一步把n-1个盘子，从A借助C移动到B第二步把第n个盘子，从A移动到B第三步把n-1个盘子，从B借助A移动到C编写递归函数voidmove(intn,charx1,charx2,charx3)表示x1上有n个盘，move函数需要把n个盘从x1上移动到x3上；x2上无盘，或x2上任何一个盘都比较x1上的所有的盘大
