递归
子程序调用自己称为递归调用，用自身的简单情况来定义自己。如
⑴求n!
⎪⎩
⎪⎨
⎧⨯-=n n )!1(1n!
⑵斐波纳契数列
⎪⎪
⎩⎪
⎪⎨⎧-+-=)
2()1(10fib(n)n fib n fib
⑶给定n （n>=1），求1+2+3+…+n 的值。
设s(n)=1+2+3+…+(n-1)+n
则 ⎪⎩⎪⎨⎧+-=n
n s n s )1(1)(
能用递归算法求解的的问题一般应该满足如下要求：
⑴符合递归的描述：需要解决的问题可以化为子问题求解，而子问题求解的方法与原问题相同，只是数
量增大与减少；
⑵递归调用的次数是有限的；
⑶必须有递归的结束条件。
归纳起来递归的两个条件：
⑴递归有边界条件。
⑵递归形式。
当n=0时 当n>0时
当n=1时 当n=2时 当n>2时
当n=1时
当n>1时
例 1、求n!
分析：根椐数学知识，0!=1，正整数N的阶乘为：N*(N-1)*(N-2)*…*2*1，该阶乘序列可转换为求N*(N-1)!，而(N-1)!以可转换为(N-1)*(N-2)!，……，直至转换为1*0!，而0!=1。
源程序如下:
program ex;
function f(n:integer):longint;
begin
if n=0 then f:=1          {递归边界}
else f:=f(n-1)*n    {递归形式}
end;
begin {main}
writeln(f(3))
end.
在过程f中，当n>1时，又调用过程f，参数为n-1，…，这种操作一直持续到n=0为止。例如当n=5时，f (5)的值变为5*f (4)，求 f ( 4)又变为4*f (3)，…，当n= 0时递归停止，逐步返回到第一次调用的初始处，返回结果5*4*3*2*1，即5!。
例2、斐波纳契数列0、1、1、2、3、5、8、13、21、34、……从第三项开始，每一项都是紧挨着的前两项之和。编程求该数列第n项。
分析：我们已经知道菲波纳葜数列的各数列的产生可用下列公式表示：
f(1)＝０f(2)＝１ f(n)＝f(n-1)＋f(n-2) （当n>2时）
因此当n大于2时，求第n项值可转化为求第n-1项值与第n-2项值的和；而求第n-1项又可转化为求n-2项值与n-3项的和，相应地，求n-2项值可转化为求n-3项值和n-4项值的和；……；如此反复，直至转化为求第1项或第2项值，而第 1项与第2项为已知值0和1。
Program ex2;
编程递归函数Var n:integer;
Function f(n:integer):longint;
Begin
Case n of
1:f:=0;          {递归边界}
2:f:=1;          {递归边界}
else f:=f(n-2)+f(n-1)  {递归形式}
end
end;  {end function}
begin  {main}
readln(n);
writeln(x(n))
end.
本程序采用了函数递归，函数F的执行比较复杂。函数F由于存在着两次的递归调用，使递归调用产生执行流程的"二叉树"形式，可参照图来理解这个执行过程。为方便起见，设定n=5，图中的数码表示递归执行的顺序。
F函数的"二叉树"执行流程
可以看出，递归过程的执行总是一个过程体未执行完，就带着本次执行的结果又进入另一轮过程体的执行，……，如此反复，不断深入，直到某次过程的执行遇到终止递归调用的条件成立时，则不再深入，而执行本次的过程体余下的部分，然后又返回到上一次调用的过程体中，执行其余下的部分，……，如此反复，直到回到起始位置上，才最终结束整个递归过程的执行，得到相应的执行结果。递归过程的程序设计的核心就是参照这种执行流程，设计出一种适合"逐步深入，而后又逐步返回"的递归调用模型，以解决实际问题。
利用递归调用程序设计技术可以解决很复杂但规律性很强的问题，并且可以使程序变得十分简短。
递归调用技术的运用，是在牺牲计算机内存空间和程序执行速度的基础上得到的。因为在递归调用的执行过程中，系统必须花费时间与空间以栈的方式记下每次调用的返回位置地址及每一次过程执行的中间结果，以便当递归调用终止条件成立时，能沿着"逐步深入"的路线"逐步返回"，取得这些数据，最终准确地回到初始调用处。比如，同是解决菲波纳葜数列问题的程序，使用递推就比使用递归算法设计的程序执行速度快了许多。
当一个问题蕴含着递归关系且结构比较复杂时，采用一般的算法，不仅给程序的设计带来许多困难，而且也会给设计出的程序带来篇幅大、可读性差的缺点，这时采用递归调用技术来设计程序则会带来
相反的效果。
例3、河内塔问题。
有n个圆盘，半径各不相同，依半径从大到小，自下而上套在A柱上，另还有B、C两根空柱，现要求将A柱上的n个圆盘全部搬到C柱上去，且每次只许搬动一个盘子，还必须始终保持每根柱子上是小盘在上，大盘在下。编一个程序能够打印出移动的过程。
A    B    C
分析：这个移动过程很复杂与烦琐，但规律性却很强。使用递归调用技术来解决这个移动过程，先得到一个递归调用模型。想要得到汉诺塔问题的简单解法，着眼点应该是移动A杆最底部的大盘，而不是其顶部的小盘。不考虑64个盘而考虑N个盘的一般情况。要想将A杆上的N个盘移至C杆，我们可以这样设想：
1.以C盘为临时杆，从A杆将1至N-1号盘移至B杆。
2.将A杆中剩下的第N号盘移至C杆。
3.以A杆为临时杆，从B杆将1至N-1号盘移至C杆。
我们看到，步骤2只需移动一次就可以完成；步骤1与3的操作则完全相同，唯一区别仅在于各杆的作用有所不同。这样，原问题被转换为与原问题相同性质的、规模小一些的新问题。即：hanoi(n,A,B,C)可转化为hanoi(n-1,A,C,B)与 hanoi(n-1,B,A,C)
其中hanoi中的参数分别表示需移动的盘数、起始盘、临时盘与终止盘，这种转换直至转入的盘数为0为止，因为这时已无盘可移了。这就是需要的递归调用模型。
A    B    C

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。