电子科技大学：《算法设计与分析 Algorithms Design and Analysis》课程教学资源（课件讲稿）第二章 递归与分治策略

第2章：递归与分治策略

第2章：递归与分治策略

知识要点 3递割归的概念和典型的递归问题 Φ阶乘、Fibonacci数列、hanoif塔等问题 ?分治法的基本思想 3分治法的典型例子 Φ二分搜索、矩阵乘法、归并排序、快速排序 Φ大整数的乘法、最接近点对问题

知识要点  递归的概念和典型的递归问题  阶乘、Fibonacci数列、hanoi塔等问题  分治法的基本思想  分治法的典型例子  二分搜索、矩阵乘法、归并排序、快速排序  大整数的乘法、最接近点对问题

2.1递归的概念

2.1 递归的概念

递归(recursion) R 什么是递归？ 程序调用自身的编程技巧称为递归 Φ 基本思路 。将一个大型的复杂问题转化为 一些与原问题相似的规模较小的问题来求解

递归(recursion)  什么是递归？  程序调用自身的编程技巧称为递归  基本思路 • 将一个大型的复杂问题转化为 • 一些与原问题相似的规模较小的问题来求解

递归(recursive) R 如果函数调用它本身，那么此函数就是递归的 3 例如n的定义就是递归的：n!=n×(n-1)川 R 考察下面的函数： int fact(int n) { 递归终止条件 if(n<=1)7/初值，1！=1 return 1; else 递归 return n fact(n -1); 表达式 } R 为了解递归的工作原理，我们来跟踪fact(4)的执行

递归(recursive)  如果函数调用它本身，那么此函数就是递归的  例如n!的定义就是递归的：n! = n × (n – 1)!  考察下面的函数： int fact(int n) { if (n <= 1) //初值，1！=1 return 1; else return n * fact(n - 1); }  为了解递归的工作原理，我们来跟踪 fact(4) 的执行 递归终止条件 递归 表达式

调用函数时系统的工作 3在调用函数时系统需要完成3件事： 将所有实参（指针），返回地址传递给被调用的函数 为被调用函数的局部变量分配存储区 将控制转移到被调用函数的入口 3从被调用函数返回时系统也要做3件事： 保存被调用算法的计算结果（返回值） 释放分配给被调用算法的存储空间 依照被调算法保存的返回地址将控制转移回到调用算法

调用函数时系统的工作  在调用函数时系统需要完成3件事：  将所有实参（指针），返回地址传递给被调用的函数  为被调用函数的局部变量分配存储区  将控制转移到被调用函数的入口  从被调用函数返回时系统也要做3件事：  保存被调用算法的计算结果（返回值）  释放分配给被调用算法的存储空间  依照被调算法保存的返回地址将控制转移回到调用算法

递归过程与递归工作栈 3递割归过程执行时需多次调用自身。多个（相同）函数 嵌套调用，信息传递和控制转移通过栈实现 Φ每一次递归调用时，需要为过程中所使用的参数、局部 变量等另外分配存储空间 层层向下递归，退出时次序正好相反 每层递归调用需分配的空间形成递归工作记录，用栈按 照后进先出规侧管理这些信息

递归过程与递归工作栈  递归过程执行时需多次调用自身。多个(相同)函数 嵌套调用，信息传递和控制转移通过栈实现  每一次递归调用时，需要为过程中所使用的参数、局部 变量等另外分配存储空间  层层向下递归，退出时次序正好相反  每层递归调用需分配的空间形成递归工作记录，用栈按 照后进先出规则管理这些信息

阶乘的递归调用过程 参数 计算 返回 0 01=1 1 0 参数 计算 返回 1 1*Factorial(0) 1 参 1 返 参数 计算 返回 数 2 2*Factorial(1) 2 2 2 回 传 参数 计算 返回 3 3*Factorial(2) 6 递 3 6 值 参数 计算 返回 4 4*Factorial(3) 24 4 24 主程序main

阶乘的递归调用过程

int main(void){ int fact(int n) int a fact(3) { recurn 0; if(n<=1) return 1; else fact(3) return n fact(n -1); ①(3<=1)不成立 ②对表达式n*fact(n-1)求值 ③调用fact(2) 6 return 3*fact(2); fact(2) ①(2<=1)不成立 ②对表达式n*fact(n-l)求值 2 ③调用fact(1)一 return 2*fact(1); fact(3) 3*fact(2) 3 fact(2) fact(1) 2*fact(1)

int fact(int n) { if (n <= 1) return 1; else return n * fact(n - 1); } fact(3) 3*fact(2) fact(2) 2*fact(1) fact(1) 2 1 1

递归的应用场景 3遇到如下三种情况，可以考虑使用递割归 1.问题定义是递归的 2.解决问题时采用的数据结构是递归定义的 3.问题的求解过程是递归的

递归的应用场景  遇到如下三种情况，可以考虑使用递归 1. 问题定义是递归的 2. 解决问题时采用的数据结构是递归定义的 3. 问题的求解过程是递归的