用递归法解决问题

用递归法解决问题

教学重点（1）了解递归现象和递归算法的特点。（2）自定义函数及递归算法的自定义函数实现。（3）培养“自顶向下”、“逐步求精”的意识。

教学难点(1)递归过程思路的建立。(2)判断问题是否适于递归解法。(3)正确写出递归程序。

递归算法递归算法作为计算机程序设计中的一种重要的算法，是较难理解的算法之一。简单地说，递归就是编写这样的一个特殊的过程，该过程体中有一个语句用于调用过程自身（称为递归调用）。递归过程由于实现了自我的嵌套执行，使这种过程的执行变得复杂起来，其执行的流程可以用图1所示。递归算法调用子程序的含义

在过程和函数的学习中，我们知道调用子程序的一般形式是：主程序调用子程序A，子程序A调用子程序B，如图如示，这个过程实际上是递归的定义：

一个函数在定义时，地调用了自己，这种算法在程序设计中统称为递归法。函数A函数B类型二函数A类型一直接或者间接递归算法递归是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。

例(1)利用递归方法编写一求N的阶乘程序。分析：根据N!=N*(N-1)*(N-2)*(N-3)*……*3*2*1

可以推出下列式子：

这是一个典型的递归算法，参考程序如下：FunctionFa(ByValnAsInteger)AsLongIfn=1ThenFa=1ElseFa=n*Fa(n-1)EndIfEndFunctionPrivateSubForm_Click()DimnAsIntegern=Val(InputBox("输入正整数N：","N！"))Print"输入的正整数是";n;Print"，阶乘是";Fa(n)EndSub程序代码自定义函数的定义格式:Functionprocedurename(arguments)[Astype]StatementsEndFunction其中：procedurename是函数名，

arguments是函数中的参数表，

type是函数返回值的数据类型，

statements是过程中的代码调用函数的格式：Procedurename(arguments)分析：可以推出下列式子：

1月2月3月4月5月6月7月8月9月10月11月12月小兔1

11235813213455大兔

1123581321345589合计1123581321345589144例(2)斐波那契(Fibonacci)数列

“兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底时将有多少对兔子?FunctionFb(ByValNAsInteger)AsLong

IfN<3ThenFb=1ElseFb=Fb(N-1)+Fb(N-2)EndIfEndFunctionPrivateSubCommand1_Click()

N=Val(Text1.Text)

Text2.Text="第"&N&"月的兔子数目是："&Fb(N)EndSub程序代码分析：第一阶第二阶第三阶例(3)爬楼梯楼梯一共有N个台阶，小明爬楼梯的方法是一步跨一个台阶或者一步跨两个台阶，于是小明开始爬楼，爬上楼以后小明提了一个问题：按刚才那样，爬完台阶一共有多少种可能的爬法？第一阶只有一种爬法：跨一步1种第二阶有两种爬法：每次只跨1步或者跨2步2种第三阶有三种爬法：有可能来自第一阶，也有可能来自第二阶3种思考：那第四阶，第五阶有多少种爬法呢那第n阶有多少种爬法呢？假设g（n）表示第n个台阶的爬法由数学知识可得递归关系式：ng(n-1)+g(n-2)n>2n≤2g(n)=递归程序如下：Privatefunctiong(byvalnasinteger)Ifn=1orn=2theng=nElseg=g(n-1)+g(n-2)EndifEndfunction思考g(n)与g(n-1)、g(n-2)关系任务：1、写出递归公式2、完成程序代码小结：递归算法的特点：

递归过程：

一般通过函数或子过程来实现。

递归算法：

在函数或子过程的内部，直接或者间接地调用自己的算法。递归算法的实质：

是把问题转化为规模缩小了的同类问题的子问题。

然后递归调用函数(或过程)来表示问题的解。

小结：一个应用递归算法解决的问题经典例子传说在古代印度的贝拿勒斯神庙，有一块黄铜板上插了3根宝石柱，在其中一根宝石柱自上而下由小到大地叠放着64个大小不等的金盘。一名僧人把这些金盘从一根宝石柱移到另外一根上。僧人在移动金盘时遵守下面3条规则：第一，一次只能移动一个金盘。第二，每个金盘只能由一根宝石柱移到另外一根宝石柱。第三，任何时候都不能把大的金盘放在小的金盘上。神话说，如果僧人把64个金盘完全地从一根宝石移到了另外一根上，世界的末日就要到了。当然，神话只能当故事来听，世界不可以因为个别人的活动而导致末日。不过，从僧人搬完64个金盘所需时间的角度来说，即使僧人每秒都能移动一个金盘，那也得要几千亿年！分析问题我们把3根宝石柱分别命名为A、B、C。最初有N个金盘放在A，需要把它们全部按规则移动到B。当N=1时，直接把金盘从A搬到B就可以了，1次成功。当N≥2，那么需要利用C柱来过渡。我们假设已经找到一种把N－1个金盘从一根柱搬到另外一根柱的方法，那么，我们只要把N－1个金盘从A搬到C，然后把最大的金盘从A搬到B，最后把C上的N－1个金盘搬到B就可以了。靠递归的思想，我们轻而易举地完成了整个搬动。设计算法

我们定义一个过程Hanoi(N，A，B，C)，表示有N个金盘需要从A柱搬到B柱(以C柱为过渡)。那么完成它只需3步：①Hanoi(N－1，A，C，B)它的意思是把A柱上的N－1个金盘搬到C柱；②

A→B

它的意思是把一个(最大的)金盘从A柱搬到B柱；③

Hanoi(N－1，C，B，A)它的意思是把c柱上的N－1个金盘搬到B柱。子程序PrivateSubHanoi(nAsInteger,ByValAAsString,ByValBAsString,ByValCAsString,tAsLong)Ifn=1ThenText3.Text=Text3.Text+A+"→"+B+“"t=t+1增加变量t用来统计移动次数。Else

CallHanoi(n-1,A,C,B,t)

Text3.Text=Text3.Text+A+"→"+B+“"

t=t+1

CallHanoi(n-1,C,B,A,t)EndIfEndSub主程序PrivateSubCommand1_Click()

DimtAsLong,nAsInteger

t=0

n=Val(Text1.Text)

A="A":

B="B":

C="C"

CallHanoi(n,A,B,C,t)

Text2.Text=tEndSub小结递归算法所体现的“重复”一般有三个要求