递推与递归(精品).ppt
递推与递归递推与递归内容摘要递推算法递归算法计算组合数汉诺塔问题快速排序问题递归思想递推与递归递推算法例题：把一张大饼置于板上，不许离开，每一刀切下去都是一条直线。问切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块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练习：斐波那契数列：1,1,2,3,5,8 a(n)=a(n-1)+a(n-2)a(0)=a(1)=1递归算法若一个过程直接或间接的调用自己，这个过程就是递归的过程一个比较复杂的问题，如果可以分解成为几个相对简单或规模较小且解法相同或类似的子问题时，只要解决了这些子问题，那么原来的问题也就可以解决了。这种策略称为分而治之法比如：求10！，只要求出子问题 9!,乘上10就得到了10!;要求 9!,只要求出了8!,乘上9就得到了9!当分解出的子问题可以直接解决时，就停止分解。直接可以解决的子问题称为递归结束条件。比如：0!=1就是结束条件递归过程可以通过编写自我调用的递归函数来简单的解决递归算法切饼问题 a(n)=a(n-1)+n也可用以下递归方法求解n=0，返回1n0,返回 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的最大公约数两个简单的例子阶乘（Factorial）：阶乘的数学表示：F(n)=n!n!=(n-1)!*nF(n)=n*F(n-1)可见，阶乘的数学表示具有递归特点。两个简单的例子阶乘（Factorial）：Factorial(n)if(n=0)return 1;/0的阶乘为1 else return n*Factorial(n-1);基础问题问题规模降阶两个简单的例子Fibonacci数列：Fibonacci数列的数学表示：F(0)=0,F(1)=1;F(n+2)=F(n+1)+F(n)(其中n=0)可见，Fibonacci数列本身就具有递归特点。两个简单的例子Fibonacci数列：Fibonacci(n)if(n=0)return 0;else if(n=1)return 1;else return Fibonacci(n-1)+Fibonacci(n-2);基本问题问题降阶递归的基本原理递归过程的两个基本要素：1.问题在每一次的递归过程中规模在变小（降阶）；2.递归的结束条件（易于解决的基本问题）。计算组合数编程实现组合计数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不在其中编程实现使用递归思想编写递归函数 int cmn(int m,int n)计算组合数汉诺塔问题据说在古代印度bramah神庙中，有个和尚整天把3根柱子上的金盘倒来倒去。初始在柱子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到n-1看作一个整体第一步把n-1个盘子，从A借助C移动到B第二步把第n个盘子，从A移动到B第三步把n-1个盘子，从B借助A移动到C编写递归函数void move(int n,char x1,char x2,char x3)表示x1上有n个盘，move函数需要把n个盘从x1上移动到x3上；x2上无盘，或x2上任何一个盘都比较x1上的所有的盘大；移动过程可以借助x2汉诺塔问题递归思想递归定义阶乘函数 a(n+1)=a(n)*(n+1)幂函数(n+1)!=n!*(n+1)斐波那契数列 f(n)=f(n-1)+f(n-2)递归数据结构链表结构，结点next指向的也是一个链表树结构，每个结点下面都是一棵子树递归算法汉诺塔解法快速排序递推与递归递推算法从头开始，通过循环迭代逐渐逼近结果使用循环语句执行效率高不易理解和写程序循环加大程序的复杂程序递归算法到着开始，每一次递归都缩小问题规模，直到问题足够小使用选择分支语句多次函数调用带来开销，效率低下比较自然的反应问题，容易理解和写程序程序清晰，结构简单递推与递归从软件工程的角度来说，递归使用程序更加简单清晰从效率角度来说，递推会比递归效率高很多清晰 VS 效率一般选择使用递推代替递归，以适当的增加程序复杂性的代价来换取效率其他问题？
