第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) 的执行 递归终止条件 递归 表达式