递归做为一种算法在程序设计语言中广泛应用。

• 中文名 递归
• 外文名 recurrence;recursion
• 分类 计算机算法

基本含义

　　​是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象。

　　在计算机编程里，递归指的是一个过程：函数不断引用自身，直到引用的对象已知。

　　使用递归解决问题，思路清晰，代码少。但是在主流高级语言中（如C语言、Pascal语言等）使用递归算法要耗用更多的栈空间，所以在堆栈尺寸受限制时（如嵌入式系统或者内核态编程），应避免采用。所有的递归算法都可以改写成与之等价的非递归算法。

　　汉诺塔问题，是常见可用递归解决的问题，不过也有非递归的解法。

　　菲波纳契数列可用递归定义。

　　以下为求汉诺塔问题的Pascal程序：

　　procedure Hanoi(n:integer;x,y,z:char);

递归

　　begin

　　if n<>1 then begin

　　Hanoi(n-1,x,z,y);

　　writeln(x,n,z);

　　Hanoi(n-1,y,x,z);

　　else writeln(x,n,z);

　　end;

　　end;

　　上述程序用接近自然语言的伪代码可表述如下：

　　Hanoi 过程 (整型参数n; 字符型参数 x,y,z);

　　//注：n 代表本步中要处理的盘子数，x,y,z 分别表示 n 号盘子原来所在柱子、经由柱子、目标柱子

　　开始

　　如果 n 不为 1 ，那么：开始

　　调用 Hanoi 过程 (参数为 n-1,x,z,y);

　　//注：这一步表示用本过程方法将剩余 n-1 个盘子从柱子 x 经由柱子 z 移动到柱子 y

　　输出 x,n,z; //注：表示将 n 号盘子从 x 移动到 z

　　调用 Hanoi 过程 (参数为 n-1,y,x,z);

　　//注：这一步表示用本过程方法将剩余 n-1 个盘子从柱子 y 经由柱子 x 移动到柱子 z

　　结束; //以上程序段就完成了把 n 个盘子从柱子 x 经由柱子 y 移动到柱子 z

　　否则 输出 x,n,z; //注：若 n 为1 的话本句直接输出表示将 n 号盘子从 x 移动到 z

　　结束;

递归定义

　　递归，就是在运行的过程中调用自己。

　　构成递归需具备的条件：

　　函数嵌套调用过程示例

　　1. 子问题须与原始问题为同样的事，且更为简单；

　　2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

　　在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

　　例如，下列为某人祖先的递归定义：

　　某人的双亲是他的祖先（基本情况）。某人祖先的双亲同样是某人的祖先（递归步骤）。斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21..... I

　　斐波纳契数列是典型的递归案例：

　　递归关系就是实体自己和自己建立关系。

　　Fib(0) = 1 [基本情况] 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)数据的定义是按递归定义的。（Fibonacci函数）

　　(2)问题解法按递归算法实现。

　　这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。

　　(3)数据的结构形式是按递归定义的。

　　如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。

　　递归的缺点：

　　递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

　　递归典型问题： 梵塔问题（汉诺塔问题）

　　已知有三根针分别用A, B, C表示，在A中从上到下依次放n个从小到大的盘子，现要求把所有的盘子

　　从A针全部移到B针，移动规则是：可以使用C临时存放盘子，每次只能移动一块盘子，而且每根针上

　　不能出现大盘压小盘，找出移动次数最小的方案.

　　如：

　　这种方式是直接调用.

　　又如：

　　这种方式是间接调用.

　　例1计算n!可用递归公式如下：

　　1 当 n=0 时

　　fac(n)={n*fac(n-1) 当n>0时

　　可编写程序如下：

　　例2 楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法.

　　设n阶台阶的走法数为f(n)

　　显然有

　　1 n=1

　　f(n)={2 n=2

　　f(n-1)+f(n-2) n>2

　　可编程序如下：

　　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,处理结束.

　　程序如下：

　　练习：

　　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)