chapter 3 归纳法.ppt

1、基于递归技术，可选的人民教师：何婉Email:第二部分，Objectives，首先将问题分成一个或多个子问题，这些个的子问题在结构上和原来的问题很相似，组合这些子问题来得到原来的问题的解，再递归技术概述递归算法的设置实现递归过程递归算法时间复杂度分析(求解递归方程)、递归技术(recursive )或间接调用自身的过程称为递归过程，将在函数本身中定义的函数称为递归函数。 例1 :阶乘函数，非递归表现： n！=123. (n-1) n n1、边界条件、递归方程式、边界条件和递归方程式是递归函数的两个要素，递归函数只具备这些个的两个要素，可在有限次校正运算后得到结果。 递归技术，示例1 :阶乘函数

2、，公共静态因子(intn ) if (n=1)返回1； if(n1) return n*factorial(n-1 ) :递归技术，示例2 :斐波那契级数无限数列1、1、2、3、5、8、13、21、34、55.示例2 :斐波那契级数无限数列1 接口(n2)返回光纤(n-1 )光纤(n-2 )。 能够由递归算法的设定纠正、递归算法实现的问题是，具有可解决在问题p的描述涉及规模，即，在P(size )规模变化之后，问题的性质不变化(有递归方程式)的问题的出口(有边界条件)，递归算法的设定纠正call P； 简单操作end； endp； 实现递归进程的实现、递归进程的关键是为进程的递归调用建立先进的

3、后向栈内存，该栈内存存储与每个调用相关的数据和相关信息，并提供此次调用所需的工作区。 只要此次调用没有结束，关于这些个的信息就会保留。 存储的信息主要包括此次调用的实际关残奥指针、进程中使用的局部变量值、此次调用结束时的回复地址等。TOP、递归过程的实现和递归过程调用所需的时间与在执行参考和每个信息上校正栈内存所需要的时间成比例。 关门时间只需要一个常数。 递归过程比非递归过程需要更多的时间和空间。 然而，这些个消耗是仅影响校正计算复杂的常数因子，不影响音量水平。 过程调用的一次使用时间乘以一次调用的时间上限，得到总时间上限。 常用递归方程来校正递归过程的时间复杂性。 递归算法的时间复杂度分析

4、、递归算法的执行时间边界都以递归形式表现，所以求解递归公式对算法分析者极为重要。 递归式也称为递归式、递归关系或递归式，递归关系解开展开递归式，解递归式的最自然的方法是用明确的方法反复展开，该方法在机械上也是直观的，实际上不需要任何说明。 但是，这种方法不灵活，也容易发生订正计算错误。求解递归关系的展开递归式，例1 :阶乘函数、公共静态因子(intn ) if (n=1) return 1； if (n1)返回函数(n-1 ) :Stirling公式： n！ 大约相等，解开递归关系展开递推公式的例子2:SelectionSort输入： n个要素的数组A1n输出：非降序数组A1n for i1

5、to n-1 /循环中指第n-1次k i /k个小要素的下标for j i 1 to n /选择要查找第I个小元素ifajajjj的排序算法的比较次数与元素输入的顺序无关，递归关系求解展开递归公式，SelectionSort输入： a1. n输出：排序的a1. n主例程： sort(1)； 调用过程：程序存储(I ) if ii then交换Ai和Ak； sort(i 1)； endif，for i1 to n-1 k i for j i 1 to n if Aji then交换Ai和Ak endfor，递归关系求出展开递归式，求出选择输入： A1.n输出：被排序的A1.n主程序：的调用程序： PP sort(i 1)； 设endif、递归方程式的定理、定理： a、b、c为非负常数、n为c的整数次方，则递归方程式的