（一）递归算法设计技术（学习笔记二）

（一）递归与数学归纳法

由上一篇学习笔记可知，递归方法的主要思路是将“大问题”分解成环境、求解过程相似的“小问题”，再由“小问题”来计算“大问题”。也就是说，如果已知 s_i , s_i+1 ,..., s_n ，我们就能很容易求出 s_n+1。从数学归纳法的角度来看，这相当于数学归纳法归纳步骤的内容。但仅有这个关系还不能确定这个数列，若使它完全确定，还应给出这个数列的初始值 s₁ ，这相当于数学归纳法的基础内容。

那下面我先给大家介绍什么是第一、第二数学归纳法原理。

第一数学归纳法原理：若 { P(1) , P(2) , P(3) , P(4) , ... } 是命题序列且满足以下两个性质，则所有命题均为真。

① P(1) 为真；

② 任何命题均可以从它的前一个命题推导得出。

第二数学归纳法原理：若 { P(1) , P(2) , P(3) , P(4) , ... } 是满足以下两个性质的命题序列，则对于其他自然数，该命题序列均为真。

① P(1) 为真；

② 任何命题均可以从它的前面所有命题推导得出。

有这两个原理可得出，数学归纳法是一种论证方法，二递归是算法和程序设计的一种实现技术，数学归纳法是递归的理论基础。

（二）递归算法设计的一般步骤

在实际应用中，用户要使用递归算法通常需要分析三个方面的问题：

① 每一次递归调用在处理问题的规模上都应有所缩小（同城问题规模可减半）；

② 相邻两次递归调用之间有紧密的联系，前一次要为后一次递归调用做准备，通常是前一次递归调用的输出作为后一次递归调用的输入；

③ 在问题的规模极小时必须直接给出问题解而不再进行递归调用，因此每次递归调用都是有条件的，无条件的递归调用将会成为死循环而不能正常结束。

所以，提取递归模型的基本步骤如下：

① 对原问题 f( s_n ) 进行分析，抽象出合理的小问题 f( s_n-1 ) （与数学归纳法中假设 n = k-1 时等式成立相似）；

② 假设 f( s_n-1 ) 是可解的，在此基础上确定 f( s_n ) 的解，即给出 f( s_n ) 与 f( s_n-1 ) 之间的关系（与数学归纳法中求证 n = k 时等式成立的过程相似）；

③ 确定一个特定情况（如 f(1) 或 f(0) ）的解，由此作为递归出口（与数学归纳法中求证 n = 1 或 n = 0 时的等式成立相似）。

用递归法求一个整数数组a中的最大元素

解题思路：

设 f( a , i ) 求解数组 a 中前 i 个元素（即 a[0,i-1] ）中的最大元素，则 f( a , i-1) 求解数组 a 中的 i-1 个元素（即 a[0,i-2]）中的最大元素，前者为大问题，后者为小问题，假设 f( a,i-1 ) 已求出，则有 f( a,i ) = MAX{ f( a , i-1 ) , a[ i-1 ] }。递推方向时朝 a 中元素个数减少的方向递推，当 a 中只有一个元素时，该元素就是最大元素，所以 f(a,1) = a[0]，由此得到递归模型如下：

f(a,i) = a[0]                      i = 1
f(a,i) = MAX{f(a,i-1),a[i-1]}      i > 1

对应的递归算法代码如下：

1 int findmax(int a[],int n)
2 {
3     if(i == 1)
4         return a[0];
5     else
6         return(findmax(a,i-1),a[i-1]);
7 }

以上就是“递归算法设计技术”的第二部分笔记，本章的学习笔记也就这两部分啦！接下来会有相关的一些例子带给大家，欢迎各位读者阅读哦！

注：“算法设计与分析”这一门课使用的计算机语言为C语言

（一）递归算法设计技术（学习笔记二）

相关推荐