高中信息技术算法与程序设计分册4.3递归法教案.docx

《高中信息技术算法与程序设计分册4.3递归法教案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.3递归法教案一、递推法概念递推法是一种数学方法，它是计算机用于数值计算中的一个重要算法。所谓递推是指针对问题利用已知条件一步一步地推出问题的解，或从问题一步一步地推出条件。引入一个例子来说明递推概念。例如：有一组数规律如下：0，5，5，10，15，25，40，...，Xn，...，我们要求Xn值，要根据前面序列数的规律找出一种运算关系。如：5=5+0，10=5+5，15=5+15，25=10+15，40=15+25，...，Xn=Xn-1+Xn-2，...。所以，当我们知道n的值时，如n=10，就可以通过前面的规律导出：每一个数就是前两个数相加得到

2、的，n=10对应的数Xn应推出为175。二、递推算法特点一个问题的求解需要一系列的计算，而已知条件和所求问题之间具有某种相互联系。如果可以找到计算过程之间的数量关系，通过这个关系可以从条件推出要解决的问题（也叫顺推）或者从问题推出已知条件（也叫逆推），这种关系被称为递推式。这种算法可以将比较复杂的运算分成若干步重复的简单运算，充分发挥计算机运算速度快的特点。例11-5编程上面的数字序列，求第n项数值。分析：由上面的分析可以得到Xn=Xn-1+Xn-2，这就是此题的数量关系式，也叫递推式。同时又有了初值x=0，y=5。根据递推算法导出程序如下：progr

3、amp11_5(input,output);varx,y,z:longint；{x,y,z存放数据序列中的数据}I,n:integer;beginwrite(‘inputn:’);read(n);{输入所求数据位，即n值}x:=0；{第一个数为0}y:=5;{第二个数为5}forI:=3tondo{从第三个数开始通过循环来实现递推式}beginZ:=y+X;{递推式}X:=y;Y:=z;{不断改变X，Y值，使X，Y一直代表前两个数}End;write(z)end.例11-6长青小学五年级一班的学生为了保护环境，利用星期日去上山植树，需要组织一部分男学生

4、去山下水库抬水浇树(两人一组)，先将这些学生排成两列纵队，可以有多少种不同组合方法。(根据个子高低，每位同学只能同同一排或前后同学组合)组合方法有：方法一：甲1乙1，甲2乙2，甲3乙3。方法二：甲1乙1，甲2甲3，乙2乙3。方法三：甲1甲2，乙1乙2，甲3乙3。因此我们得出队列的排数与组合的方法数有如下关系：两列纵队有一排(2个人)组合方法一种即：x1=1二排(4个人)二种即：x2=2三排(6个人)三种即：X3=X1+X2⋯⋯⋯最终导出有n排时(有2n个人)组合方法是：Xn=Xn-l+Xn-2。此题的递推式是从问题推到已知：从Xn

5、=Xn-l+Xn-2，推到Xn-1=Xn-2+Xn-3，...X2=2,X1=1。推到程序：programp11_6(input，output)；varX,y,Z:longint；j,n:integer;beginread(n);x:=0;y:=1;forj:=1tondo{设循环变量j为纵队的排数}beginz:=x+y;{z是不同排数时的组合方法数}X:=y;y:=z;End;write(‘有’,n,’排男生参加抬水组合方法有’,z);end．思考：自己能找出还有哪些问题可以用递推算法来解决?递归就是函数或过程的调用，递归包括直接递归和间接递

6、归。能用递归算法来求解的问题一般应该满足三个条件即：需要解决的问题可以化为子问题，而子问题的求解方法与原问题的求解方法相同，只有数量的差别：递归调用的次数有限；有递归结束的条件。因此，分析每一个问题首先要按以上三条来检查一下是否适合应用递归算法。例11-7用递归方法编写程序，根据n的值运算f的结果，关系式如下：(也是斐波那契数列中第n个数的求解关系式)算法一、利用递归程序：programp11_7a(input,outpu);varm,p:integer;functionfib(n:integer):integer;beginifn=0thenfib:

7、=0elseifn=1thenfib:=1elsefib:=fib(n-1)+fib(n-2)enk;beginreadln(m);p:=fib(m);writeln(p);end.这是一个直接调用函数本身的直接递归法，它是根据从大到小的处理方法，也就是先把flb(n)拆分为fib(n-1)和fib(n-2)，直拆分到fib(0)和fib(1)结束，递归次数最多2n-1次。递归使一些复杂的问题处理起来简单明了，尤其在学习算法设计、数据结构时更能体会到这一点。但是，递归在每次执行时都要为局部变量返回地址分配栈空间，这就降低了运行效率，也就影响了递归算法的

8、应用。算法2：递推算法按从小到大顺序讨论fib(0)=0,fib(1)=1,fib(2)=fi