c语言_递归算法.ppt

《c语言_递归算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机语言与程序设计谌卫军清华大学软件学院IntroductiontoComputerProgramming第八章递归算法132基本概念基于回溯策略的递归基于分治策略的递归从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚，老和尚正在给小和尚讲故事。讲的是什么故事呢？他说，从前……Recursion-See"Recursion"."Inordertounderstandrecursion,onemustfirstunderstandrecursion."C语言允许嵌套地调用函数，也就是说，在调用一个函数的过程中，又去调用另一个函数

2、。函数的嵌套调用voidmain(){…study_english();…}voidstudy_english(){reading();listening();writing()}voidlistening(){………}函数的嵌套调用有一个特例，即递归调用，也就是说，在调用一个函数的过程中，又出现了直接或间接地去调用该函数本身。voidtell_story(){intold_monk,young_monk;tell_story();//tell_story函数的递归调用}函数的递归调用?voidtell_story(){static

3、intold_monk,young_monk;old_monk=old_monk+1;//年龄大了一岁young_monk=young_monk+1;if(old_monk<=60)//递归形式tell_story();elseprintf("对不起，已退休！");//递归边界}在语法上（简单）递归即为普通的函数调用。在算法上（难）如何找到递归形式？如何找到递归边界？如何编写递归程序？递归算法的类型递归算法可以分为两种类型：基于分治策略的递归算法；基于回溯策略的递归算法。第八章递归算法132基本概念基于回溯策略的递归基于分治策略的递

4、归分而治之（divide-and-conquer）的算法设计思想：Divide：把问题划分为若干个子问题；Conquer：以同样的方式分别去处理各个子问题；Combine：把各个子问题的处理结果综合起来，形成最终的处理结果。8.2.1分而治之玛特露什卡……调用调用……调用调用……调用调用如何编写基于分治策略的递归程序？在算法分析上，要建立分治递归的思维方式。在编程实现上，要建立递归信心（Totursttherecursion,JerryCain,stanford）。如何建立分治递归的思维方式？基本原则：目标驱动！计算n!：n!=n*

5、(n-1)!，且1!=1。递归形式递归边界调用调用fact(3)fact(2)fact(1)voidmain(){intn;printf("请输入一个整数：");scanf("%d",&n);printf("%d!=%d",n,fact(n));}intfact(intn){if(n==1)return(1);elsereturn(n*fact(n-1));}请输入一个整数：33!=6调用和返回的递归示意图如何建立递归信心？函数的递归调用到底是如何进行的呢？在递归调用时，执行的是不是相同的代码？访问的是不是相同的数据？如果是的话

6、，那么大家会不会相互干扰、相互妨碍？main的栈帧m3voidmain(){intm;printf("请输入一个整数：");scanf("%d",&m);printf("%d!=%d",m,fact(m));}intfact(intn){if(n==1)return(1);elsereturn(n*fact(n-1));}3nfact的栈帧2nfact的栈帧1nfact的栈帧8.2.2寻找最大值问题描述：给定一个整型数组a，找出其中的最大值。如何设计相应的递归算法？如何来设计相应的递归算法？目标：max{a[0],a[1],…a

7、[n-1]}可分解为：max{a[0],max{a[1],…a[n-1]}}另外已知max{x}＝x这就是递归算法的递归形式和递归边界，据此可以编写出相应的递归函数。intMax(inta[],intfirst,intn){intmax;if(first==n-1)returna[first];max=Max(a,first+1,n);if(max

8、法问题描述：查找（Searching）：根据给定的某个值，在一组数据（尤其是一个数组）当中，确定有没有出现相同取值的数据元素。顺序查找、折半查找。前提：数据是有序排列的；基本思路：将目标值与数组的中间元素进行比较；若相等，查找成功。否