程序调用自身的编程技巧称为递归（ recursion）。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 注意： (1) 递归就是在过程或函数里调用自身(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

　递归算法一般用于解决三类问题： (1)数据的定义是按递归定义的。(Fibonacci函数) (2)问题解法按递归算法实现。(回溯) (3)数据的结构形式是按递归定义的。(树的遍历，图的搜索) 递归的缺点： 递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。 例子： #include <iostream.h>void move (char getone,char putone) { cout <<getone<<"-->"<} void hanoi(int n,char one ,char two ,char three) { void move (char getone,char putone )if (n==1) move (one,three)else { hanoi(n-1,one,three,two)move (one ,three)hanoi(n-1,two,one,three)} } void main() { void hanoi(int n ,char one ,char two ,char three)int m cout <<"Input the numberof disker:"cin>>mcout<<"the steps to moving "<<m<<"diskes :"<<endlhanoi(m,'A','B','C')} 如: procedure abegin aend这种方式是直接调用. 又如: procedure bbegin cendprocedure cbegin bend这种方式是间接调用. 例1计算n!可用递归公式如下: 1 当 n=0 时 fac(n)={n*fac(n-1) 当n>0时 可编写程序如下: program fac2var n:integerfunction fac(n:integer):realbegin if n=0 then fac:=1 else fac:=n*fac(n-1)； endbegin write('n=')readln(n)writeln('fac(',n,')=',fac(n):6:0)end. 例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法. 设n阶台阶的走法数为f(n) 显然有 1 n=1 f(n)={2 n=2 f(n-1)+f(n-2) n>2 可编程序如下： program loutivar n:integerfunction f(x:integer):integerbegin if x=1 then f:=1 else if x=2 then f:=2 else f:=f(x-1)+f(x-2)endbegin write('n=')read(n)writeln('f(',n,')=',f(n)) end. 2.2 如何设计递归算法 1.确定递归公式 2.确定边界(终了)条件 练习: 用递归的方法完成下列问题 1.求数组中的最大数 2.1+2+3+...+n 3.求n个整数的积 4.求n个整数的平均值 5.求n个自然数的最大公约数与最小公倍数 6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子? 7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项. 2.3典型例题 例3 梵塔问题 如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子 从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上 不能出现大盘压小盘.找出移动次数最小的方案. 程序如下: program fantavar n:integerprocedure move(n,a,b,c:integer)begin if n=1 then writeln(a,'--->',c) else begin move(n-1,a,c,b)writeln(a,'--->',c)move(n-1,b,a,c)endendbegin write('Enter n=')read(n)move(n,1,2,3)end. 例4 快速排序 快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束. 程序如下: program kspvvar a:array[0..10000] of longinti:integerprocedure quicksort(l,r:longint)var i,j,mid:longintbegin i:=lj:=rmid:=a[(l+r) div 2]repeat while a[i]<mid do inc(i)while a[j]>mid do dec(j)if i<=j then begin a[0]:=a[i]a[i]:=a[j]a[j]:=a[0]inc(i)dec(j)until i>jif i<r then quicksort(i,r)if l<j then quicksort(l,j)endbegin write('input data:')readln(n)for i:=1 to n do read(a[i])writelnquicksort(1,n)write('output data:')for i:=1 to n do write(a[i],' ')writelnend.

递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身，每调用一次就进入新的一层。递归函数必须有结束条件。

当函数在一直递推，直到遇到墙后返回，这个墙就是结束条件。

所以递归要有两个要素，结束条件与递推关系。

递归有两个基本要素：

（1）边界条件：确定递归到何时终止，也称为递归出口。

（2）递归模式：大问题是如何分解为小问题的，也称为递归体。递归函数只有具备了这两个要素，才能在有限次计算后得出结果

在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。

一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：

（1）运动开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；

（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；

（3）每次递归调用结束后，将栈顶元

扩展资料：

递归就是某个函数直接或间接地调用了自身，这种调用方式叫做递归调用。说白了，还是函数调用。既然是函数调用，那么就有一个雷打不动的原则：所有被调用的函数都将创建一个副本，各自为调用者服务，而不受其他函数的影响。

你的ff函数，递归多少次，就有多少个副本，再利用内存的栈式管理，反向退出。这个最好找一下“栈”这方面的东西看看，挺容易的，就像子弹匣一样，先进后出。

从某种意义上说，这是不对的，因为就像刚才说的，一旦被调用，他将在内存中复制出一份代码，再被调用就再复制一份，换句话说，你可以吧同一个函数的多次调用理解称谓多个不同函数的一次调用，这样也会会简单些。

再说=1和=0是为什么退出。递归，很需要注意的就是死递归，也就是说，某一个函数进入了无限调用自身的情况，永无止境地消耗内存等资源，这在编程方面是一大忌。

但凡是递归的函数，一定会在某一个地方存在能够返回上一层函数的代码，否则必定死递归。ff函数中，那个else就是返回的出口，你可以这样想，如果没有那个if来进行判断，你递归到什么时候算完？ff是不是会一直调用自己。

因为一旦某个函数A中调用了函数B（或者自己），那么A中的代码会停在调用的位置，而转向B中去执行，同理，如果B又调用函数C，那么B又停在调用的位置，去执行C，如果无限调用，那么程序是永远不会结束的。

当然，也有这种情况，A调用B，然后继续自己的代码，不管B的死活，这种不在我们的讨论范围内，因为那牵扯到另一种编程方式：多线程。

参考资料：百度百科——递归函数

一个子程序（过程或函数）的定义中又直接或间接地调用该子程序本身，称为递归。递归是一种非常有用的程序设计方法。用递归算法编写的程序结构清晰，具有很好的可读性。递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。

利用递归算法解题，首先要对问题的以下三个方面进行分析：

一、决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。

二、问题的边界条件及边界值。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。

三、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。把这些步骤或等式确定下来。

把以上三个方面分析好之后，就可以在子程序中定义递归调用。其一般格式为：

if 边界条件 1 成立 then

赋予边界值 1

【 elseif 边界条件 2 成立 then

赋予边界值 2

┇ 】

else

调用解决问题的通式

endif

例 1 ： 计算勒让德多项式的值

x 、 n 由键盘输入。

分析： 当 n ＝ 0 或 n ＝ 1 时，多项式的值都可以直接求出来，只是当 n ＞ 1 时，才使问题变得复杂，决定问题复杂程度的参数是 n 。根据题目提供的已知条件，我们也很容易发现，问题的边界条件及边界值有两个，分别是：当 n ＝ 0 时 P n (x) ＝ 1 和当 n ＝ 1 时 P n (x) ＝ x 。解决问题的通式是：

P n (x) ＝ ((2n － 1)P n － 1 (x) － (n － 1)P n － 2 (x)) ／ n 。

接下来按照上面介绍的一般格式定义递归子程序。

function Pnx(n as integer)

if n ＝ 0 then

Pnx ＝ 1

elseif n ＝ 1 then

Pnx ＝ x

else

Pnx ＝ ((2*n － 1)*Pnx(n － 1) － (n － 1)*Pnx(n － 2)) ／ n

endif

end function

例 2 ： Hanoi 塔问题：传说印度教的主神梵天创造世界时，在印度北部佛教圣地贝拿勒斯圣庙里，安放了一块黄铜板，板上插着三根宝石针，在其中一根宝石针上，自下而上地放着由大到小的 64 个金盘。这就是所谓的梵塔（ Hanoi ），如图。梵天要求僧侣们坚持不渝地按下面的规则把 64 个盘子移到另一根针上：

(1) 一次只能移一个盘子；

(2) 盘子只许在三根针上存放；

(3) 永远不许大盘压小盘。

梵天宣称，当把他创造世界之时所安放的 64 个盘子全部移到另一根针上时，世界将在一声霹雳声中毁灭。那时，他的虔诚的信徒都可以升天。

要求设计一个程序输出盘子的移动过程。

分析： 为了使问题更具有普遍性，设共有 n 个金盘，并且将金盘由小到大依次编号为 1 ， 2 ，…， n 。要把放在 s(source) 针上的 n 个金盘移到目的针 o(objective) 上，当只有一个金盘，即 n ＝ 1 时，问题是比较简单的，只要将编号为 1 的金盘从 s 针上直接移至 o 针上即可。可定义过程 move(s,1,o) 来实现。只是当 n>1 时，才使问题变得复杂。决定问题规模的参数是金盘的个数 n ；问题的边界条件及边界值是：当 n ＝ 1 时， move(s,1,o) 。

当金盘不止一个时，可以把最上面的 n － 1 个金盘看作一个整体。这样 n 个金盘就分成了两个部分：上面 n － 1 个金盘和最下面的编号为 n 的金盘。移动金盘的问题就可以分成下面三个子问题（三个步骤）：

(1) 借助 o 针，将 n － 1 个金盘（依照上述法则）从 s 针移至 i(indirect) 针上；

(2) 将编号为 n 的金盘直接从 s 针移至 o 针上；

(3) 借助 s 针，将 i 针上的 n － 1 个金盘（依照上述法则）移至 o 针上。如图

其中第二步只移动一个金盘，很容易解决。第一、第三步虽然不能直接解决，但我们已经把移动 n 个金盘的问题变成了移动 n － 1 个金盘的问题，问题的规模变小了。如果再把第一、第三步分别分成类似的三个子问题，移动 n － 1 个金盘的问题还可以变成移动 n － 2 个金盘的问题，同样可变成移动 n － 3 ，…， 1 个金盘的问题，从而将整个问题加以解决。

这三个步骤就是解决问题的通式，可以以过程的形式把它们定义下来：

hanoi(n － 1,s,o,i)

move(s,n,o)

hanoi(n － 1,i,s,o)

参考程序如下：

declare sub hanoi(n,s,i,o)

declare sub move(s,n,o)

input "How many disks?",n

s ＝ 1

i ＝ 2

o ＝ 3

call hanoi(n,s,i,o)

end

sub hanoi(n,s,i,o)

rem 递归子程序

if n ＝ 1 then

call move(s,1,o)

else

call hanoi(n － 1,s,o,i)

call move(s,n,o)

call hanoi(n － 1,i,s,o)

endif

end sub

sub move(s,n,o)

print "move disk"n

print "from"s"to"o

end sub

---