程序调用自身的编程技巧称为递归。递归作为一种算法在程序设计语言中广泛应用。
定义
一般定义
程序调用自身的编程技巧称为递归（ recursion）。
一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
注意：
(1) 递归就是在过程或函数里调用自身；
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
递归的另一种定义：
递归，就是在运行的过程中调用自己。
在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
例如，下列为某人祖先的递归定义：
某人的双亲是他的祖先（基本情况）。某人祖先的双亲同样是某人的祖先（递归步骤）。斐波纳契数列（斐波那契 法里数列），又称斐波那契数列，指的是这样一个数列：1、1、2、3、5、8、13、21..... I
斐波纳契数列是典型的递归案例：
Fib(0) = 0 [基本情况] Fib(1) = 1 [基本情况] 对所有n > 1的整数：Fib(n) = (Fib(n-1) + Fib(n-2)) [递归定义] 尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：
阶乘（1) = 1 [基本情况] 对所有n > 1的整数：阶乘（n) = (n * 阶乘（n-1)) [递归定义] 一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这是你已经知道该怎么做的。
如此的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。
德罗斯特效应是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片，进而小图片中还有更小的一幅她手持同一物体的图片，依此类推。
又例如，我们在两面相对的镜子之间放一根正在燃烧的蜡烛，我们会从其中一面镜子里看到一根蜡烛，蜡烛后面又有一面镜子，镜子里里又有一根蜡烛……这也是递归的表现。
算法特点递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。递归算法要求递归算法所体现的“重复”一般有三个要求：一是每次调用在规模上都有所缩小(通常是减半)；二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
应用
递归应用递归算法一般用于解决三类问题：(1)数据的定义是按递归定义的。（斐波那契函数）(2)问题解法按递归算法实现。（回溯）(3)数据的结构形式是按递归定义的。（树的遍历，图的搜索）递归的缺点：递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
例子：
如： procedure a; begin a; end; 这种方式是直接调用. 又如： procedure b; begin c; end; procedure c; begin b; end; 这种方式是间接调用.
例1计算n!可用 递归公式如下： 1 当 n=0 时 fac(n)={n*fac(n-1) 当n>0时 可编写程序如下： program fac2; var n:integer; function fac(n:integer):real; begin if n=0 then fac:=1 else fac:=n*fac(n-1)； end; begin 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 louti; var n:integer; function f(x:integer):integer; begin if x=1 then f:=1 else if x=2 then f:=2 else f:=f(x-1)+f(x-2); end; begin write('n=');read(n); writeln('f(',n,')=',f(n)) end.
例3 梵塔问题如图：已知有三根针分别用1,2,3表示，在一号针中从小放n个盘子，现要求把所有的盘子 从1针全部移到3针，移动规则是：使用2针作为过度针，每次只移动一块盘子，且每根针上 不能出现大盘压小盘。找出移动次数最小的方案. 程序如下： program fanta; var n:integer; procedure 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); end; end; begin write('Enter n='); read(n); move(n,1,2,3); end.
例4 快速排序 快速排序的思想是：先从数据序列中选一个元素，并将序列中所有比该元素小的元素都放到它的右边或左边，再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1,处理结束. 程序如下： program kspv; var a:array[0..10000] of longint; i:integer; procedure quicksort(l,r:longint); var i,j,mid:longint; begin i:=l;j:=r;mid:=a[(l+r) div 2]; repeat while a[i] while a[j]>mid do dec(j); if i<=j then begin a:=a[i];a[i]:=a[j];a[j]:=a; inc(i);dec(j); until i>j; if i if l end; begin write('input 数据:'); readln(n); for i:=1 to n do read(a[i]); writeln; quicksort(1,n); write('output data:'); for i:=1 to n do write(a[i],' '); writeln; end. 练习： 1.计算ackerman 函数值: n+1 m=0 ack(m,n)={ ack(m-1,1) m<>0,n=0 ack(m-1,ack(m,n-1)) m<>0,n<>0 求ack(5,4)
参考资料 >