7.3.8 递归式算法求解问题

出它的解,从而得到原来问题的解。
3.采用递归算法需具备的条件 (1)每一步骤解决问题的方法要一致。
(2)要有结束的边界条件。
必考+加试·信息技术
【典例1】小明利用下面的方法求2i(2的i次方)的值:如果i=0,则 2i=1,否则
将2i转换为2*2i-1 ,而2i-1 又可以转换为2*i-2, 如此继续,从而求出了2i的值。
必考+加试·信息技术
第四单元
递归算法
必考+加试·信息技术
考点与典例
考点 递归算法 1.递归的概念 函数或过程调用其本身,称为递归。 2.递归算法的基本思想 递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容 易解决的同一问题 , 规模较小的问题又变成规模更小的问题 , 直到可以直接得
If n=0 Then f=1 Else f=f(n-1)+5 End If End Function Private Sub Command1_Click() Dim y As Long
必考+加试·信息技术
y=f(5)
Label1.Caption=Str(y)
End Sub 程序运行时,单击命令按钮Command1后,在标签Label1中显示的内容是 ( A.1 ) B.5
C.21 D.26
必考+加试·信息技术
解析:本题考查的是递归算法的程序实现。这段程序有两部分组成:事件处理
过 程 (Private Sub Command1_Click()) 和 自 定 义 函 数 (Function f(n As
Integer) As Long) 。 在 自 定 义 函 数 f 中 又 出 现 了 调 用 函 数 f 本 身 的 语 句 f=f(n-1)+5,因此f函数采用的是递归算法。 在事件处理过程Private Sub Command1_Click()中,语句y=f(5)表示调用函 数f,将参数5传递给f函数中的变量n,最终将函数的返回值赋给变量y。 y=f(5)= 5+5+5+5+5+1=26,因此在标签Label1中显示的内容为26。 答案:D

一．递归算法概述程序调用自身的编程技巧称为递归（ recursion）。

一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。

用递归思想写出的程序往往十分简洁易懂。

二．递归算法的特点递归算法是一种直接或者间接地调用自身算法的过程。

在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。

递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。

所以一般不提倡用递归算法设计程序。

(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。

递归次数过多容易造成栈溢出等。

所以一般不提倡用递归算法设计程序。

三．递归算法要求递归算法所体现的“重复”一般有三个要求：一是每次调用在规模上都有所缩小(通常是减半)；二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。

四．例子（用从C＋＋描述）：行数程序#include <iostream>using namespace std;0 void p (int w){1 if(w>0){2 cout<<w<<" ";3 p(w-1);4 p(w-1);5 }6 }void main(){int a;cin>>a;p(a);}当输入a=4后的打印结果：当p（0）执行完了，就会执行p(1)中的语句5（所以在方格a中，填“5”）。

【算法复习】求解递归式的⽅法求解递归式的⽅法【代⼊法】代⼊法求解分为两步：猜测解的形式⽤数学归纳法求出解的常数C，并证明正确性，关键步骤是⽤猜测的解代⼊到递归式中。

做出好的猜测（没有⼀般⽅法，只能凭经验）与见过的解类似，则猜测之。

先证较宽松的上、下界，减⼩猜测范围。

我们可以从下界Ω(n)开始，上界O(n^2)，然后逐渐收敛⾄(nlog2n)细节修正有时猜测解是正确的，但数学归纳法却不能直接证明其细节，这是因为数学归纳法不是强⼤到⾜以证明其细节。

这时可从猜测解中减去⼀个低阶项以使数学归纳法得以满⾜避免陷阱与求和式的数学归纳法类似，证明时渐近记号的使⽤易产⽣错误。

如：证明O(n)时必须严格证明≤cn，不能讲其换做cn+n变量变换有时改动变量能使未知递归式变为熟悉的式⼦。

例如：【代⼊法例题】【递归树法】递归树最适合⽤来⽣成好的猜想，然后可⽤代⼊法来验证猜测是否正确需要关注：达到边界条件所需的迭代次数迭代过程中的和式。

若在迭代过程中已估计出解的形式，亦可⽤代⼊法【递归树法例题】【Master原理】Master定理也叫主定理。

它提供了⼀种通过渐近符号表⽰递推关系式的⽅法。

应⽤Master定理可以很简便的求解递归⽅程。

定理4.1（主定理）令a≥1和b>1是常数，f(n)是⼀个函数，T(n)是定义在⾮负整数上的递归式： T(n) = aT(n/b) + f(n)其中我们将n/b解释为。

那么T(n)有如下渐近界：主定理的三种情况，经过分析，可以发现都是把f(n)与⽐较。

第⼀种情况是更⼤，第⼆种情况是与f(n)相等，第三种情况是f(n)更⼤。

【主定理例题】。

递归算法详解what：在计算机科学中是指⼀种通过重复将问题分解为同类的⼦问题⽽解决问题的⽅法when：发现问题可以分解为同类⼦问题且采⽤同样的⽅式去解决how：找到递归出⼝和递归体步骤：通过分析题⽬是否可以分解为若⼲重复⼦问题，判断是否可以采⽤递归算法进⾏解决。

确定采⽤递归算法之后，开始找递归出⼝和递归体，这是递归算法的核⼼部分，下⾯通过两个题⽬讲⼀下我的解题步骤。

P1：leetcode226 翻转⼆叉树简单题解答：题⽬很简单，翻转⼆叉树，然后查看输⼊输出，其实就是将每个节点的左右⼦树进⾏了交换。

这个时候⼦问题已经出现了，交换左右⼦树，按题⽬说法就是翻转左右⼦树，可以采⽤递归来做。

接下来需要找到递归出⼝和递归体，⼀般情况下先找递归体，因为确定递归的时候⼤概就已经确定了递归体，然后就是考虑边界问题，确定递归出⼝。

回到题⽬，根据题⽬的分析，可以确定递归体即为交换翻转当前节点的左右⼦树，当遍历⾄根节点⽆节点可翻转时即退出递归，即找到递归出⼝当前节点为null。

接下来代码实现：public class Solution{/** 226. 翻转⼆叉树简单题**/public TreeNode invertTree(TreeNode root) {this.invert(root);return root;}private void invert(TreeNode root){if (null == root) {return;}TreeNode left = root.left;TreeNode right = root.right;root.right = invertTree(left);root.left = invertTree(right);}}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val;}TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}P2：leetcode24，给定⼀个链表，两两交换其中相邻的节点，并返回交换后的链表。