第5课 递归Word下载.docx
《第5课 递归Word下载.docx》由会员分享，可在线阅读，更多相关《第5课 递归Word下载.docx（14页珍藏版）》请在冰点文库上搜索。
……直到最后求出n！
。
参考程序：
Programexample1（input,output）;
Var
n,i:
integer；
s:
real；
Functionfac（t:
integer）:
real;
begin
ift=0
thenfac:
=1;
递归调用示意图
elsefac:
=fac（t-1）*t;
end;
Begin
readln（n）；
=fac（n）;
{函数调用}
Writeln（n,‘!
=’,s）；
End.
函数递归调用的过程是当在函数中遇到调用自身的时候会等着它的前一个项目继续通过递归调用的形式计算出结果，而前一个项目又会等着前前一个项目计算出结果，依次深入，直到直接得到结果的最底层，然后逐层向后返回，最终求得结果。
例题2：
求m与n的最大公约数。
X*n+（mmodn）n
从数学上可以知道求m和n的最大公约数等价于求n与（mmodn）的最大公约数，这时可以将n当作新的m，（mmodn）当作新的n，问题又变成了求新的m和n的最大公约数，如此继续，直到新的n等于0时，其最大公约数就是m。
求最大公约数的函数gcd（m,n）可以转换为以下的公式：
m
n
16
24
8
Programexample2（input,output）;
m,n,g:
Functiongcd（m,n:
integer;
ifn=0
thengcd:
=m;
elsegcd:
=gcd（n,mmodn）;
read（m,n）；
g:
=gcd（m,n）;
Writeln（g）；
例题3：
汉诺塔问题，如下图，有A、B、C三根柱子。
A柱子上按从小到大的顺序堆放了N个盘子，现在要把全部盘子从A柱移动到C柱，移动过程中可以借助B柱。
移动时有如下要求：
（1）一次只能移动一个盘子；
（2）不允许把大盘放在小盘上边；
（3）盘子只能放在三根柱子上；
算法分析：
当盘子比较多的时，问题比较复杂，所以我们先分析简单的情况：
如果只有一个盘子，只需一步，直接把它从A柱移动到C柱；
如果是2个盘子，共需要移动3步:
（1）把A柱上的小盘子移动到B柱，即A→B;
（2）把A柱上的大盘子移动到C柱，即A→C；
（3）把B柱上的大盘子移动到C柱，即B→C；
如果N比较大时，我们先考虑是否能把复杂的移动过程转化为简单的移动过程，如果要把A柱上最大的盘子移动到C柱上去，必须先把上面的N-1个盘子从A柱移动到B柱上暂存。
我们定义一个过程move，为了将n个盘子从a经过b移动到c上，可以调用过程move（n,a,b,c）。
按照上面的这种思路，就可以把N个盘子的移动过程分作3大步：
（1）把A柱上面的N-1个盘子移动到B柱，调用move（n-1,a,c,b）；
（2）把A柱上剩下的一个盘子移动到C柱，即为A→C；
（3）把B柱上面的N-1个盘子移动到C柱，调用move（n-1,b,a,c）；
其中N-1个盘子的移动过程又可按同样的方法分为三大步，这样就把移动过程转化为一个递归的过程，直到最后只剩下一个盘子，按照移动一个盘子的方法移动，递归结束。
递归过程：
procedureHanoi（N,A,B,C:
integer）；
{以B柱为中转柱将N个盘子从A柱移动到C柱}
begin
ifN=1
thenwriteln（A,’--->
’,C）{把盘子直接从A移动到C}
elsebegin
Hanoi（N-1,A,C,B）；
{以C柱为中转柱将N-1个盘子从A柱移动到B柱}
writeln（A,’--->
’,C）；
{把剩下的一个盘子从A移动到C}
Hanoi（N-1,B,A,C）；
{以A柱为中转柱将N-1个盘子从B柱移动到C柱}
end;
从这个例子我们可以看出，在使用递归算法时，首先弄清楚简单情况下的解法，然后弄清楚如何把复杂情况归纳为更简单的情况。
完整的参考程序：
Programexample3（input,output）;
n:
read（n）;
mov（n,1,2,3）;
{用1，2，3分别代表A，B，C}
end.
通过上面的几个例题我们可以看出，递归算法的设计思路有两点：
1.确定递归公式
2.确定边界（终了）条件
递归公式通常在取值比较大的时候可能比较好构建，比如求n!
、求最大公约数、汉诺塔游戏等，在此情况下首先应该找到规律，看看本步骤能不能转化为前步骤的条件下的简单实现，最后再确定边界条件而在过程或函数中控制结束。
有时候递归公式可能不太好找，比如下面的一个例子：
例题4：
用递归的方法求n个数中最大的数及其位置。
（其中n为指定常量，比如10）
这个题目看上去没法得出类似于上面例题中的通用递归公式。
但是我们可以这样考虑，从第2个数开始，我们每一个数都可以和它前面所有数中的最大数进行比较，从而找出当前情况下的最大数，然后继续用下一个数比较，得出其中的最大数，直到最后一个数试完，我们就得到了所有数中的最大数。
具体算法：
从第一个数开始，每次都去比较下一个数a[I+1]与这个数前面所有数中的最大数的大小，如果后来的数a[I+1]比它前面最大的数还大，则将其下标记住，下一个数再比较的时候就与这个数进行比较，直到最后一个数比较完为止。
参考程序如下：
Programexample4;
Const
n=10;
Type
arr=array[1..n]ofinteger;
Var
a:
arr;
p,j:
{p用来在程序运行过程中记住前面部分数据中最大值的位置}
Procedurefindmax（I:
varp:
integer）;
{p为变量参数}
Begin
IfI<
=n
thenbegin
Ifa[I]>
a[p]
thenp:
=I;
Findmax（I+1,p）;
end
End;
BEGIN
Forj:
=1tondo
read（a[j]）;
Readln;
p:
Findmax（2,p）;
Writeln（‘bigest=’,a[p]:
4,’position=’,p:
4）;
END.
递归有时候可以实现不能确定循环层数的多重循环功能，此种情况下通常是通过递归实现的回溯功能，我们下一节会讲到。
例题5：
求N个数的全排列。
（1~N）
当n=3时我们可以使用多重循环来做：
forI:
=1to3do
forj:
ifI<
>
j
thenfork:
if（k<
I）and（k<
j）
write（i,’’,j,’’,k）;
但当n的值不确定的时候，循环层数无法确定，无法使用多重循环。
我们可以这样考虑，求N个数的全排列，可以看成把N个不同的球放入N个不同的盒子中，每个盒子中只能有一个球。
在过程中使用循环来放置每一个可能的值到第一个盒子中，然后将其它的数用同样的方式放到后面的第2个盒子中，再把除掉这两个数的其它数用同样的方式放到后面的第3个盒子中，以此类推，可以使用循环来做，但不知道需要多少层循环，我们可以做成递归的形式，即在过程中调用自身，调用之前应该做的工作应该是将前面用过的数排除掉。
我们可以定义两个相同下标的数组，其中一个数组x用来放数，另一个数组a用来表示该数有没有被前面放置过，未放置则其值为true，放置过之后其值置为false。
数据结构定义：
1、设数组a为N个空盒可以放N个数，一开始数组a全部置为true，表示都可以放，放完之后置为false，表示不可以放了。
2、设数组x是放置每一次排列的数组，在过程中try应该是从第1个数组元素开始的，而下一次的递归调用其下标应该逐次加1，即调用try（i+1）;
3、Total为累记总数
参考过程：
proceduretry（i:
{调用的时候确定x[i]的值}
var
j:
forj:
=1tondo
ifa[j]=true
x[i]:
=j;
a[j]:
=false;
{某一个数被用过之后，在后面的递归调用中不能再用}
ifi<
n{控制递归的结束，即出口}
thentry（i+1）{递归调用确定下一个数组元素x[i+1]的值}
elseprint;
{过程，用于调用打印输出一次排列}
a[j]=true;
{下一次再选择另一个数时释放前面用过的数}
programexample5;
var
i,n,total:
x,a:
array[1..9]ofinteger;
procedureprint;
{该过程用来打印输出一次排列}
i:
fori:
write（x[i],′′）;
writeln;
total:
=total+1;
{每打印一次累加一次，记住排列的个数}
{选择可能的数据放置在数组x[i]中}
x[i]:
a[j]:
ifi<
n
thentry（i+1）
=true;
=0;
writeln（'
Pleaseinputn'
）;
readln（n）;
a[i]:
try
（1）;
{首先应该确定的是数组x[1]中应该放置的数}
total='
total）;
readln;
end.
有些问题本身是递归定义的，但它并不适合用递归算法来求解，如斐波那契（Fibonacci）数列，它的递归定义为：
F（n）=1（n=1,2）
F（n）=F（n-2）+F（n-1）（n>
2）
用递归过程描述为：
Funtionfb（n:
ifn<
3
thenfb:
=1
elsefb:
=fb（n-1）+fb（n-2）;
上面的递归过程，调用一次产生二个新的调用，递归次数呈指数增长，时间复杂度为O（2n）,把它改为非递归：
x:
y:
=3tondo
begin
z:
=y;
=x+y;
=z;
修改后的程序，它的时间复杂度为O（n）。
我们在编写程序时是否使用递归算法，关键是看问题是否适合用递归算法来求解。
由于递归算法编写的程序逻辑性强，结构清晰，正确性易于证明，程序调试也十分方便，在NOIP中，数据的规模一般也不大，只要问题适合用递归算法求解，我们还是可以大胆地使用递归算法。
【递归程序与非递归程序的差异】
递归程序与非递归程序的主要差别在于返回数据和保存递归函数调用现场的内存需求量。
执行递归程序时须考虑下列两种状况。
1、每次递归调用一个函数时：
a.存储适当的返回位置和目前递归函数调用现场的值。
b.把现场的值设置为新值。
2、每当一个递归调用完成后：
a.将最后一次存储的数据，返回给目前的返回数据和递归函数调用现场。
b.返回这个调用函数的适当位置，或者当最初调用完成时则返回执行最初调用的程序。
当此程序并不符合返回值的函数情况时，我们可以修改程序使它合乎这个情况。
或者我们也可以使额外的函数参数通过指针返回值。
被存储起来的数据（返回位置和函数调用现场的值），必须依据其被存储的相反顺序被取回。
除了这些存储数据必须在其函数的区域范围内使用之外，与非递归程序并没有两样。
我们可以将返回值和递归函数调用现场值想象成一个记录所记载的事，因此，记录集就类似于被暂停的递归调用必须存储在某些数据结构之中。
注意，此时的数据结构不仅存储了这些记录，并且包括了这些记录的前后次序。
【递归程序与非递归程序中循环的差异】
循环是指反复执行某些条件，直到符合所指定的条件为止，但不包含函数引用自己本身。
它和递归的差异：
1.循环用while、for或repeat，而递归用If…else来控制循环。
2.递归用较多的参数及较少的局部变量。
【递归的效率问题】
一般而言，一个非递归程序在时间及空间上都比递归程序有效率（见下表），主要的原因是隐含的进出递归程序的操作和不必要的栈操作很多，在非递归程序中存在大量不需要栈的当地变量和临时位置，但是在递归程序中，编译器通常无法识别这种变量而增加了栈过程。
在某些情况下，递归解法是解决问题的一种最自然且合乎逻辑的方式，利用递归解法可能使得程序设计师不需花费太多的精力就能够解决问题，但是程序的执行效率可能会变差，机器效率和程序设计者效率就有待评估分析。
如果程序经常要执行，执行速度的提高很有必要，则在程序设计上花较多的时间是一项值得的投资。
在这种情况，模拟、转换递归解决为非递归解法比直接由问题叙述去求解来得容易。
其步骤是首先写出问题的递归形式，然后转换成模拟形态，包括准备所有栈和临时地址，接着除去多余的栈和变量，最后得到一有效的程序。
在除去这种多余的地址和不必要的运算过程中，可能导致一些不必要的错误，因此必须非常小心。
递归
非递归
程序可读性
易
难
代码量大小
小
大
时间
长
短
占用stack
练习:
用递归的方法完成下列问题
1.求数组中的最大数
2.1+2+3+...+n
3.求n个整数的积
4.求n个整数的平均值
5.求n个自然数的最大公约数与最小公倍数
6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?
7.已知:
数列1,1,2,4,7,13,24,44,...求数列的第n项.
升级会员 