C语言递归算法.ppt

计算机语言与程序设计;第八章 递归算法;从前有座山，山上有座庙，庙里有一个老和尚 和一个小和尚，老和尚正在给小和尚讲故事。 讲的是什么故事呢？他说，从前……;Recursion - See Recursion. In order to understand recursion, one must first understand recursion. ;C语言允许嵌套地调用函数，也就是说，在调用 一个函数的过程中，又去调用另一个函数。;函数的嵌套调用有一个特例，即递归调用，也就 是说，在调用一个函数的过程中，又出现了直接 或间接地去调用该函数本身。;void tell_story( ) { static int old_monk, young_monk; old_monk = old_monk + 1; // 年龄大了一岁 young_monk = young_monk + 1; if(old_monk = 60) // 递归形式 tell_story ( ); else printf(对不起，已退休！); // 递归边界 };在语法上（简单） 递归即为普通的函数调用。 在算法上（难） 如何找到递归形式？ 如何找到递归边界？;递归算法的类型;第八章 递归算法;分而治之（divide-and-conquer）的算法 设计思想： Divide：把问题划分为若干个子问题； Conquer：以同样的方式分别去处理各个子问题； Combine：把各个子问题的处理结果综合起来，形成最终的处理结果。;玛特露什卡;……;如何编写基于分治策略的递归程序？ 在算法分析上，要建立分治递归的思维方式。 在编程实现上，要建立递归信心（To turst the recursion, Jerry Cain, stanford）。; 如何建立分治递归的思维方式？ 基本原则：目标驱动！ 计算n!：n! = n * (n-1)!，且1! = 1。;调用;void main( ) { int n; printf(请输入一个整数：); scanf(%d, n); printf(%d! = %d \n, n, fact(n)); } int fact(int n) { if(n == 1) return(1); else return(n * fact(n-1)); };调用和返回的递归示意图; 如何建立递归信心？ 函数的递归调用到底是如何进行的呢？在递归调用时，执行的是不是相同的代码？访问的是不是相同的数据？如果是的话，那么大家会不会相互干扰、相互妨碍？;main的栈帧;8.2.2 寻找最大值;如何来设计相应的递归算法？ 目标：max{a[0], a[1], … a[n-1]} 可分解为：max{a[0], max{a[1], … a[n-1]}} 另外已知max{x} ＝ x 这就是递归算法的递归形式和递归边界，据 此可以编写出相应的递归函数。;int Max(int a[], int first, int n) { int max; if(first == n-1) return a[first]; max = Max(a, first+1, n); if(max a[first]) return a[first]; else return max; };8.2.3 折半查找法;前提：数据是有序排列的； 基本思路： 将目标值与数组的中间元素进行比较； 若相等，查找成功。否则根据比较的结果将查找范围缩小一半，然后重复此过程。;4120243;4120243;4120243;4120243;4120243;void main() { int b[] = {05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92}; int x = 21; printf(x位于数组的第%d个元素\n, bsearch(b, x, 0, 10)); };函数原型：int bsearch(int b[], int x, int L, int R); 递归的形式？ 递归的边界？;int bsearch(int b[], int x, int L, int R) { int mid; if(