第二章分治和递归

2.1 递归

2.1.1 递归的定义

? ? ? ? ① 程序调用自身的编程技巧称为递归。

? ? ? ? ② 递归的基本思路：将一个大型问题转化为一些与原问题相似的规模较小的问题来求解。

? ? ? ? ③ 如果函数调用他本身，那么他就是递归的。

2.1.2 递归的应用场景

? ? ? ? ① 问题的定义是递归的：例如斐波拉契数列。

? ? ? ? ② 解决问题采用的数据结构是递归定义的：例如二叉树的遍历

? ? ? ? ③ 问题的求解过程是递归的：例如汉诺塔问题

2.1.3 递归式

? ? ? ? 递归式是用于描述递归函数的数学公式，斐波拉契数列便是一个典型的例子，举例如下：

????????

????????其满足：

????????① 第一式给出了函数的初始值，称为边界条件

? ? ? ? ② 第二式用较小的自变量函数值来描述大自变量的函数值，称为递归方程

? ? ? ? ③ 递归方程和边界条件是递归的两个基本要素

2.1.4 斐波拉契数列的简单实现

? ? ? ? ① 程序实现如下：

long int fib(int n) {
	// 边界条件
	if (n <= 1) 
	{
		return 1;
	}
	else
	{
		// 递归方程
		return fib(n - 1) + fib(n - 2);
	}
}

??????② 以n = 4，即fib(4)程序运行如下：

2.1.5 递归的使用条件

? ? ? ? ① 原始问题可以分解成相似的子问题

? ? ? ? ② 子问题的规模小于原始问题

? ? ? ? ③ 递归函数必须有某些类型的终止条件

2.1.6 递归的优缺点

????????

递归优点

结构清晰，易于理解，容易用数学归纳法来证明算法正确性

递归缺点

执行时多次调用自身，运行效率较低，所耗费的时间空间都比非递归算法多。

某些运算步骤可能重复计算，进一步降低效率

2.2 分治

2.2.1 分治的设计思想

分治法的设计思想，即是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

????????分治模式在每一层递归上的步骤。

? ? ? ? ① 分解（Divide）: 将一个难以直接解决的大问题，分割成一些规模较小的子问题，这些子问题相互独立，且与原问题相同。

? ? ? ? ②求解（Conquer）:递归求解子问题，若问题足够小则直接求解。

? ? ? ? ③合并（Combine）:将各个子问题的解合并得到原问题的解。

2.2.2 二分搜索法的简单实现

????????

// a[]为已经升序排列好的数组，x为查找的目标，left和right为当前分区的左右数组下标
int BinarySearch(int a[], int x, int left, int right) {
    // right >= left 表示还有数据未检索
    while (right >= left) {
        // 获取升序排列数组的中间值的下标
        int mid = (left + right) / 2;
        // 如果目标值与数组值相等，返回数组下标
        if (x == a[mid]) return mid;
        // 如果目标值小于数组值，左边数组下标不变，右边数组下标选取mid - 1
        if (x < a[mid]) right = mid - 1;
        // 如果目标值大于数组值，右边数组下标不变，左边数组下标选取mid + 1
        else left = mid + 1;
    }
    // 没有找到对应元素返回-1
    return -1;
}

? ? ? ? ?① 数组a[ i ]为排序好的升序数组，如果传入数组为乱序，则不可使用此方法。