递归和分治

递归

递归的定义

子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，称为递归。

递归是一种描述问题和解决问题的基本方法。

递归的要素

1. 递归边界条件：

   确定递归何时终止，也称为递归出口；

2. 递归模式：

   大问题是如何分解为小问题的，也称为递归体。

递归过程与递归工作栈

• 递归过程在实现时，需要自己调用自己；
• 层层向下递归，返回次序正好相反

斐波那契序列

递归求解

非递归求解

回文串

如果一个字符串从左向右读和从右向左读完全相同（不区分大小写），则这个字符串称为回文串（palindrome），例如“noon”，“madam”等都是回文串。

递归求解

非递归求解

分治递归

总体思想

1. 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。

2. 将求出的小规模的解合并为一个更大规模的问题的解，自底向上逐步求出原来的解。

适用条件

分治法能解决的问题一般具有一下几个特征：

• 该问题的规模缩小到一定程度就可以容易的解决；

  ==因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征==。

• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

  ==这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用。==

• 利用该问题分解出的子问题的解可以合并为该问题的解；

  ==能否应用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法和动态规划。==

• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

  ==这条特征涉及到分治法的效率，如果各个子问题是不独立的，则分治法要做许多不必要的工作，重复的解公共的子问题，此时虽然也可以用分治法，但一般用动态规划较好。==

基本步骤

平衡子问题

平均分的子问题规模要比非平均分的效果好。

复杂性分析

复杂度计算

代换法

忽略技术细节

主要思想

1. 猜测解的形式
2. 通过数学归纳法找出使解真正有效的常数。

例子

迭代法（递归树方法）

思想

模拟该递归关系执行过程，从而计算算法运行时间

分类

• 直接展开（algebraic）
• 递归树（geometrical）

直接展开

展开递归关系式并将该展开式的递归关系表达成仅依赖于n和初始条件的各项之和的形式。

递归树

• 画出递归关系式的递归树
• 树中每个节点都代表递归函数调用集合中一个子问题的代价
• 每一层的代价相加得到一个每层代价的集合
• 层代价相加得到递归的总代价

复杂例子

结论

• 递归树最适合用来产生好的猜测，然后用代换法加以验证。产生猜测时，可以容忍小的不良量，因为后面会证明所做的猜测；
• 如果使用递归树非常仔细，所有代价都累加了起来，则可以直接用递归树作为递归式解的证明。

主方法

应用

打印n个数的全排列

算法思想

算法实现

性能分析

棋盘覆盖

问题描述

性能分析

大整数乘法

• 如何存储任意大的整数？
• 加法和乘法的复杂度分别是多少？能否改进？

• 如何存储矩阵数据？
• 传统两个矩阵的乘法复杂度是多少？能否改进？