《递归法》ppt-教科版选修1

ppt课件
14
int fib(int n) { if (n==0) return 0; if (n==1) return 1; return (fib(n-1)+fib(n-2)); }
输入 15 输出 fib(15)=610
//满足边界条件，递归返回 //满足边界条件，递归返回 //递归公式，进一步递归
//调用下一层递归
}

int main()
{
int n,k;

cin >> n >> k;

cout << s(n,k);

return 0;
}
ppt课件
19
【例6】数的计数(Noip2001)
【问题描述】
我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一 个自然数n（n≤1000），然后对此自然数按照如下方法进行处理：
8
ppt课件
9
假设把第3步，第4步，第7步抽出来就相当于N=2的情况（把上面2片 捆在一起，视为一片）：
ppt课件
10
所以可按“N=2”的移动步骤设计：
①如果N=0，则退出，即结束程序;否则继续往下执行;
②用C柱作为协助过渡，将A柱上的（N-1）片移到B柱上，调用过程mov(n-1,
a,b,c);
本题是典型的递归程序设计题。 (1)当N=1 时，只有一个盘子，只需要移动一次:A—>C; (2)当N=2时，则需要移动三次：
A------ 1 ------> B, A ------ 2 ------> C, B ------ 1------> C. (3)如果N=3，则具体移动步骤为：

题的运行效率较低。所以一般不提倡用递归算法 设计程序
递归法的归纳2：
递归算法所体现的“重复”一般有三个要求： 一是每次调用在规模上都有所缩小(通常是减半)； 二是相邻两次重复之间有紧密的联系，前一次要为
后一次做准备(通常前一次的输出就作为后一次的 输入)； 三是在问题的规模极小时必须用直接给出解答而不 再进行递归调用，因而每次递归调用都是有条件 的(以规模未达到直接解答的大小为条件)，无条 件递归调用将会成为死循环而不能正常结束。
• 注意：必须要有一个结束递归的条件，不 得无限递归。
分析步骤：
• 1.决定问题规模的参数。 • 2.问题的边界条件及边界值。 • 3.解决问题的通式。
例:计算一个数的阶乘
• 1!=1 • 2!=1*2 • 3!=1*2*3 • 4!=1*2*3*4 • 5!=1*2*3*4*5 • ……. • n!=1*2*3*4*5*….*n
函数是为了实现某种功能而编写的一段相对独立 的程序。
• 标准函数
Abs( ) 、len( )、mid( )、chr( )、asc( )……
• 自定义函数
自定义函数是指我们自己编写的函数。
自定义函数:
• 在VB中，自定义函数形式如下： • [Public|Private] Function <函数名称> ([参数列表]) [As
f(1)=1 f(2)=f(1)*2 f(3)=f(2)*3 f(4)=f(3)*4 f(5)=f(4)*5 …….. f(n)=f(n-1)*n
递归函数求5！
• Public Function s(n As Integer) As Long
• If n = 1 Then
• s =1
• Else

递归实例4
循环日程表问题。 n=8个运动员的日程表，填充方式见下面
一个8*8(23的方阵) 的矩阵，可以分为4*4（22的方阵）的 四个矩阵，设其分别A,B,C,D,则A=B,C=D=A+4
递归实例4
循环日程表问题
void circulateSchedule(int n) { // 递归出口 if(n == 1) { return ; } // 将2^k*2^k的表格分成2^(k-1)*2^(k-1)的四个子表格,构造第1个子表 int half = n / 2; circulateSchedule( half); // 填充余下三个子表 for(int i=0; i<half;i++) for(int j=0;j<half;j++) { table[half+i][half+j] = table[i][j]; table[i][ half+j] = table[ half+i][j] = table[i][j] + half; }
“汉诺塔”（Hanoi）
这是一个必须用递归方法才能解决的问题
n=64时， 18,446,744,073,709,551,615次 1844亿亿次 每次1微秒，需要60万年
递归问题分析
第一步：将问题简化。
假设A杆上只有2个圆盘，即汉诺塔有2层，n＝
2。 A
B
C
递归问题分析
递归实例3——解决复杂问题
汉诺塔——汉诺塔问题是最经典的只能够使用
递归的方法解决的问题，题目描述如下：
据传说，在古代世界中心的贝拿勒斯（印度北部）的圣庙 里，一块在黄铜 板上插着3根宝石针。印度教的主神梵天 在创造世界时，在其中的一根针上自下而上地穿好了由大 至小的64层金片，即为汉诺塔。无论白天黑夜，总有一个 僧侣按 如下的法则移动这些金片，一次只能够移动一层 ，不管在哪根针上，小片必须在大片的上面。 要求借助 于第二根针将整个汉诺塔移至第三根针上。

什么是递归算法? 递归算法：是一种直接或者间接地调用自身 的算法。在计算机编写程序中，递归算法对 解决一大类问题是十分有效的，它往往使算 法的描述简洁而且易于理解。
斐波那契的兔子问题 某人有一对兔子饲养在围墙中，如果 它们每个月生一对兔子，且新生的兔子 在第二个月后也是每个月生一对兔子， 问一年后围墙中共有多少对兔子。
递 归 算 法
主讲人：位胜楠
老师今天在查看英文文献的时候，遇 到了一些问题。 每次遇到不懂的单词都头痛不已，但是 老师只有英译英的词典，那么，可想而知， 遇到第一个不懂的单词时，查看词典，词 典的解释又全是英文，看第一个单词的解 释时，又遇到第二个不懂的单词，就这样， 继续查看第二个单词的解释， 同样的情况，在第二个单词解释中又遇到 第三个不认识的单词，幸运的是第三个单 词的解释老师全都认识，那么，很明显知 道了第三个解释，就知道了第二个，知道 了第二个就知道了第一个， 最后不认识的单词都知道了。这个过程， 就是递归。
Private Sub Command1_Click()
n = Val(Text1.Text)
If n < 3 Then c = 1 Else a = 1: b = 1 For i = 3 To n
c=Text = "第" & n & "月的兔子数目是：" & c End Sub
递归算法的特点
递归过程一般通过函数或子过程来实 现。
递归算法：
在函数或子过程的内部，直接或者间 接地调用自己的算法。
递归算法的实质：是把问题转
化为规模缩小了的同类问题的子问题。 然后递归调用函数(或过程)来表示问 题的解。
列函数
运用学过的自定义函数知识，结合之前分析的递归思想列出函数，更 加深入理解递归的特点。

4563697
4564531 4565926
正中间 的元素
4566088
4572874
17
4120243
4276013
4328968 4397700
4462718
请问： 4565926是否在 此列表当中？ 4565925？
4466240 4475579
4478964
4480332 4494763
4499043
相应的参数来完成，这就是函数或子程序，使用时只需对其名字进行
简单调用就能来完成特定功能。

例如我们把上面的讲故事的过程包装成一个函数，就会得到：
void Story() { puts("从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故 事，它讲的故事是："); getchar();//按任意键听下一个故事的内容 Story(); //老和尚讲的故事，实际上就是上面那个故事 }
4563697
4564531 4565926
4566088
4572874
16
4120243
4276013
4328968 4397700
4462718
请问： 4565926是否在 此列表当中？
4466240 4475579
4478964
4480332 4494763
4499043
4508710 4549243

(1)对原问题f(s)进行分析,假设出合理的“较小 问题” f(s')( 与数学归纳法中假设 n=k-1时等式 成立相似)； (2)假设f(s')是可解的,在此基础上确定f(s)的解, 即给出 f(s) 与 f(s') 之间的关系 ( 与数学归纳法中 求证n=k时等式成立的过程相似)； (3)确定一个特定情况(如f(1)或f(0))的解,由此 作为递归边界(与数学归纳法中求证n=1时等式 成立相似)。

写成函数形式，则为：
当n 0时 1 f ( n) n * f (n 1) 当n 0时
这种函数定义的方法是用阶乘函数自己本身定义了 阶乘函数，称上式为阶乘函数的递推定义式。
数学归纳法表明，如果我们知道某个论点对最小的情 形成立，并且可以证明一个情形暗示着另一个情形，那么我 们就知道该论点对所有情形都成立。 数学有时是按递归方式定义的。 例1：假设S（n）是前n个整数的和，那么S（1）= 1，并且 我们可以将S（n）写成S（n）= S（n-1）+ n。 根据递归公式，我们可以得到对应的递归函数： int S(int n) { if (n == 1) return 1; else return S(n-1) + n; } 函数由递归公式得到，应该是好理解的，要想求出S （n），得先求出S(n-1)，递归终止的条件（递归出口）是(n == 1)。
↑
low 第二次: 下标 元素值 0 1 1 3 2 4
↑
mid 3 5 4 17 5 18 6 31
↑
high 7 33
↑
low 第三次: 下标 元素值 0 1 1 3 2 4 3 5 4 17
↑
mid 5 18 6 31
↑
high 7 33
↑
low high mid
• Public static void main(String args[]) •{ • int[] shus={1,3,4,5,17,18,31,33};
求Fib(5)的递归计算过程如图所示。
Fib(5) Fib(4) Fib(3) Fib(2) Fib(1) Fib(2) Fib(3) Fib(2) Fib(1) Fib(0)
Fib(1) Fib(0) Fib(1)

12
3. 问题的求解方法是递归的
• 一个典型的例子是在有序数组中查找一个数据元素是否存在的折半 查找算法
第三种递归
有序数组元 素为1；3； 4;5;17;18;3 1;33; 寻找值为17 的数据
13
折半查找中的递归现象总结
折半查找无非就是三种情况，其中两种情况的问 题解法如果以算法来表示，都存在算法调用自身 的情况。 递归算法的特点就是：将问题分解成为形式上更 加简单的子问题来进行求解。递归算法不但是一 种有效的分析问题方法，也是一种有效的算法设 计方法，是解决很多复杂问题的重要方法。
根据以上数学 定义，函数f能 否写成左边所 示？函数能否 调用自身？
答案是肯定的。 C系统会保证 调用过程的正 确性，这就是 递归！
29
递归的定义： int f(int n) 从程序书写来看，在定义一个 { 函数时，若在函数的功能实现部 if(n == 0) 分又出现对它本身的调用，则称 return 1; 该函数是递归的或递归定义的。 else return n * f(n-1); 从函数动态运行来看，当调用 一个函数A时，在进入函数A且 } 还没有退出（返回）之前，又再 一次由于调用A本身而进入函数 A，则称之为函数A的递归调用。
递归出口
19
• 递归模型的分解过程不是随意分解，分解问题规模要保证 “大问题”和“小问题”的相似性，即求解过程和环境要具 备相似性； • 一旦遇到递归出口，分解过程结束，开始求值，分解是量变 的过程，大问题慢慢变小，但是尚未解决，遇到递归出口之 后，发生了质变，即递归问题转化为直接问题。 • 因此，递归算法的执行总是分为分解和求值两个部分。
20
• 递归出口的一般格式如下 • f(s1)=m1 • 递归体的一般格式 • f(sn)=g(f(sn-1),c) • 递归的分解过程 • 递归求值的过程

想一想
2．public sub f(byval n as long ) Dim a as long a=a+n print n end sub
3．Public Function f(byval a as integer)as integer dim b as integer f=f(a,b) end fuction
试一试 经典数学问题
1）1+2+3+……N 2）N！
知识回顾
1、递归分为 （ ） 与（ ） 两个过程。
2、下面哪个问题可以用递归法解决？
（1）钻石图案
（2）百鸡百钱
（3）加密程序
（4）汉诺塔
3、只要调用函数都是递归法？
4、递归法必需要有结束条件？
现实生活 → 一层梦境 → 二层梦境 → 三层梦境 → 四层梦境 现实生活 ← 一层梦境 ← 二层梦境 ← 三层梦境 ← 四层梦境
从前有座山，山里有个庙，庙里
有个老和尚讲故事，讲什么呢？ 从前有座山，山里有个庙……
从前有座山
你的眼睛 他的眼睛
如果一个函数在定义时，直接
或间接地调用了自己，这种算 法在程序设计中统称为递归法。
函数A
函数A 函数B
和尚移盘
一个庙里有三个柱子（A，B，C），第一 个柱子（ A ）有7个盘子，从上往下盘子越来越 大。要求庙里的老和尚把这7个盘子全部移动到 第三个柱子（ C）上。
递归算法有什么特点?
1、递归法：函数直接或间接地调用了自己
2、递归分为递推（问题下推）与回归（结 果回归）两个过程
3、递归必需要有结束条件 4、递归函数的调用方式相当耗费计算机资源， 因而其效率比较低
想一想
1．Public Function story( byval n as integer ) as integer If n==0 then end else story=story(n-1) end if end Function

A(1,1)=2故A(n,1)=2*n ❖ M=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和
A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2^n 。
2 222
❖ M=3时，类似的可以推出
n
❖ M=4时，A(n,4)的增长速度非常快，以至于没有适当的数 学式子来表示这一函数。
❖
move(a,b);
❖
hanoi(n-1, c, b, a);
❖
}
❖}
❖ T(n)=2T(n-1)+O(1) n≥1
T(n)=2n-1
0
n=0
4
27
简单递归式的求解
1.T(n)=T(n-1)+c1 n>1
c2
n=1
2. T(n)=2T(n/2)+c1 n ≥2
c2
n<2
3. T(n)=2T(n/2)+Θ(n) n ≥2
O(1)
n<2
28
T( n/2 ) + T( n/2 ) + 1
例1 T(n) =
0
(n = 1)
解 ：T(n)=2T(n/2)+1
=22T(n/22)+2+1
=23T(n/23)+22+2+1
令2r=n =2rT(1)+2r-1+。。。+2+1
=(1-2r)/(1-2)=n-1
∴ T( n ) = n - 1
25
递归算法的时间复杂度分析
❖ 递归函数求解
简单递归式求解 master method 递推方程的特征方程求解

时你们上体育课是怎么报数的？
前面我们学习了自定义函数，知道函数是为 了实现某种功能而编写的一段相对独立的程 序，并且可以多次的调用。 算法描述： function what ( student ) 如果我知道答案，那么我就告诉你 否则，我要问下一位同学再告诉你 end function
一、标准函数
VB给我们提供了一些标准函数，我们不用了解这些函数如 何求出来的，只管直接调用它们。如正弦函数，余弦函数，算术 平方根等，有了这些函数，解决问题很方便。如：求1加到100的 算术平方根这个程序，我们可以这样编写：
例1
Dim i as integer
Dim s as single
s=0
for i=1 to 100
虽然VB为我们提供了大量的标准函数，但我们 在实际应用时难免会找不到合适的，于是只有自己 编写函数解决问题，这样为了一个特定的任务而编 出来的函数叫自定义函数。
自定义函数的作用
1、可以方便地把较为复杂的问题分解成若干 个小问题去处理。(公司里就是采用这种模式的。)
2、使程序结构清晰，层次分明，增强了程序 的可读性。
fun=2 else fun=1 end if End function
Private sub form _ click() dim I as integer,s as integer s=0 For I=1 to 5 s=s+fun(I) Next I Print s End sub
典型例题
有一天小猴子摘若干个桃子,当即吃了一半 还觉得不过瘾,又多吃了一个。第二天接着吃 剩下桃子中的一个，仍觉得不过瘾又多吃了 一个，以后小猴子都是吃尚存桃子一半多一 个。到第10天早上小猴子再去吃桃子的时候 ，看到只剩下一个桃子。问小猴子第一天共 摘下了多少个桃子?

递归问题的提出
第一步：将问题简化。 – 假设A杆上只有2个圆盘，即汉诺塔有2层，n＝2。
A
B
C
递归问题的提出
A
B
C
对于一个有 n（n>1）个圆盘的汉诺塔，将n个圆盘分 为两部分：上面的 n-1 个圆盘和最下面的n号圆盘。将 “上面的n-1个圆盘”看成一个整体。
– 将 n-1个盘子从一根木桩移到另一根木桩上
1
当n 1时
n ! n (n 1)! 当n 1时
long int Fact(int n)
{ long int x;
if (n > 1)
{ x = Fact(n-1);
/*递归调用*/
return n*x; }
else return 1;
/*递归基础*/
}
Fact(n) 开始 传进的参数n N n>1
两种不同的递归函数--递归与迭代
21
(2)递归和迭代有什么差别?
递归和迭代(递推)
迭代(递推)：可以自递归基础开始，由前向后依次计算或直
接计算；
递归：可以自递归基础开始，由前向后依次计算或直接计算；
但有些，只能由后向前代入，直到递归基础，寻找一条路径， 然后再由前向后计算。
递归包含了递推(迭代)，但递推(迭代)不能覆盖递归。
递归的概念 (5)小结
战德臣 教授
组合 抽象
构造 递归
用递归 定义
用递归 构造
递归计 算/执行
递归 基础
递归 步骤
两种不同的递归函数
递归
迭代
两种不同的递归函数--递归与迭代
20
(1)两种不同的递归函数?
递归和递推：比较下面两个示例

简单的递归（Hanoi塔问题）
设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这 些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号 为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍 按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中 任一塔座上。

}

}
简单的递归（纵向显示整数）

停止条件
如果问题足够简单，就可以不用递归调用解
决。对于writeVertical，这发生在 number只有一位时。这种没有任何递归的 情况叫做停止条件或基本条件。在 writeVertical方法中，停止条件由三行 代码实现： if(number<10){
top top
) w=3 3 （(1 1）
(2) 2 （2 ）w=2 (1) 3 （1 ）w=3
(3) 1 （ 3）w=1 (2) 2 （ 2）w=2 3 （(1) 1）w=3
（4 ）w=0 (4) 0 （3 ）w=1 (3) 1 （2 ）w=2 (2) 2 （1 ）w=3 (1) 3
简单的递归（十进制转二进制）
简单的递归（纵向显示整数）
方法writeVertical的实现

public static void writeVertical(int number){
if(number<10){

System.out.println(number);
}else{
writeVertical(number/10); System.out.println(number%10);

基于归纳的递归算法(n阶多项式)
算法 HORNERERC 输入：非负正数n, 实数序列a0, a1,…, an和实数x 输出：n次多项式Pn(x)=anxn + an-1xn-1 +…+ a1x + a0的值 1 hn(n, x) 过程 hn(m, x) 1 if m=0 then 2 return an 3 else 4 p=x*hn(m-1, x)+ an-m 5 return p 6 end if

1 2

if n=0 then return 1 else return n*fatorial(n-1)
递归关系(特性)：产生递归的基础。 递归出口(结束条件)：确定递归的层数。 参数设置：参数表示了原问题及其不同的子问题。
基于归纳的递归算法(归纳的思想方法)
（2）归纳法的思想方法
对于一个规模为n的问题p(n)，归纳法的思想方法是：

基础步：a1是问题p(1)的解。 归纳步：对所有的k，1kn，若b是问题p(k)的解，则p(b)是 问题p(k+1)的解。其中， p(b)是对问题的某种运算或处理。
例如。因为a1是问题p(1)的解，若a2=p(a1)， a2是问题p(2)的解； 以此类推，an-1是问题p(n-1)的解，且an=p(an-1)， 则an是问题p(n)的解。 因此，求解问题p(n)的解an ，可先求问题p(n-1)的解an-1 ，然后 再对an-1进行p运算或处理。为求问题p(n-1)的解，先求问题p(n-2)的解， 如此不断进行递归求解。直至p(1)为止。当得到p(1)的解之后，再返回 来，不断地把所得的解进行p运算或处理，直至p(n)的解为止。这就是 基于归纳的递归算法的思想方法。