递归 (计算机科学)
 |
此条目没有列出任何参考或来源。（2008年6月20日） 请协助添加来自可靠来源的引用以改善这篇条目。 无法查证的内容可能被提出异议而移除。 |
在计算机编程里，递归指的是一个过程：函数不断引用自身，直到引用的对象已知。
使用递归解决问题，思路清晰，代码少。
河内塔问题，是常见可用递归解决的问题，不过也有非递归的解法。
菲波纳契数列可用递归定义。
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
结束;
一般的计算机程序由多个程序段落组成，现代结构化编程语言使用函数或者方法来组织这些段落。不论程序语言基于何种框架，这些段落之间总保持着某种互相调用的机制。如果编程语言使用函数或者方法来组织，大多数时候我们称这样的调用叫做呼出（Call）函数或者呼出方法。
当然也有很多现代化的手段使用配置文件等各种形式来进行非显式的调用，不过这是当前主题的题外话了。
就像上述的河内塔问题一样，递归是简化问题解决步骤的手段之一。不过看了上面的例子之后仍有不少人会迷惑为什么要使用递归，虽然他们可能已经理解了所谓递归就是程序段落呼出自己。
列举一个更接近生活的例子，树形的文件目录。假设你在D盘（由于Windows已经是民用微机OS的事实标准所以我在这里采用Windows的名词来解释我的例子，无意冒犯任何非MS OS拥护者）建立了一些文件夹和文件，希望将不论存在于哪个文件夹之中的所有文件的文件名列举出来（假定为将这些文件名写在一张纸上好了）。
首先要说明的是Windows采用的树形结构；上面的例子中要求列举树形结构中所有的文件，不论他在树型结构中的那个分支（文件夹）上。这种行为在数据结构中称为遍历，遍历又有n多种，不过又超出了当前标题的范围就是了。
回到我们的例子，想象一下你自己如何来完成这项工作。我猜过程大致就是这样的：
1、打开第一个文件夹，看看里面有没有子文件夹，如果有就打开第一个字文件夹，直到打开某个子文件夹时该文件夹下没有子文件夹了，这个时候我们将该文件夹下所有的文件名抄下来。
2、回到上一层文件夹，打开刚才没有打开过的文件夹重复第1步的工作。如果该层没有没有开过的子文件夹了就回到上一层重复第2步的工作。
这样我们就可以把所有的文件无一遗漏的抄在纸上。
当然你也可以倒过来做这件事就像某些读者心理所想的那样，一旦打开某个文件夹就抄下所含的所有文件的文件名，而后再去考虑打开子文件夹的问题。OK，当然这也可以。我不否认还有按心情好坏随意挑选文件夹打开，随意抄写几个或者全部文件的文件名。经过n次打开关闭操作后，也许可能能够得到正确的结果，总之我在此暂不推荐就是了。
回到我们刚才的2步操作，细心的读者可能发现，其实这2步操作重复的是同一件事：如果存在没有访问的子文件夹就打开他，没有就抄下当前文件夹下的所有文件名并回到上一层文件夹（如果没有上一层文件夹呢？其实就是我们将D盘下所有的文件名都抄完后准备回到“我的电脑”的状况。当然，我们不会去回到“我的电脑”，因为此时此刻预定的任务已经完成了）。
如果到此为止您一时无法接受我上一段落的突然的、崩塌式的归纳，我建议您随手建立一些文件夹和文件尝试一下。而后你会发觉前面花了2个段落描述的繁杂操作原来确实如此的简单。
正因为我们的操作如此简单，所以如果来写程序的话我们一般都会选择把这个逻辑写在一个段落中，而后可以在某个位置通过某种手段不断的重复调用这个段落来达到目的。我想不少读者读到此都会这么想。不过经过我们这么一说，也许你又有了另一种想法：递归呢？（特别说明小品用于说明递归，而不是抄写文件名）
其实我们可以只调用一次这个程序段落，尔后的所有问题都交给他自己去解决。仔细想想我的归纳“如果存在没有访问的子文件夹就打开他，没有就抄下当前文件夹下的所有文件名并回到上一层文件夹”，这里有两个关键字“打开”和“回到”。不论是打开没有访问过的子文件或是回到上一层的文件夹，其实就是在重复整个操作本身所作的操作。可能比较拗口，再换种说法：“打开”或者“回到”之后的步骤又是“如果存在没有访问的子文件夹就打开他，没有就抄下……”。恩，请相信我，这就是所谓的递归。
话已至此可能关于递归问题已经解释清楚了，不过还差一个重要的概念没有特别说明。还记得“回到‘我的电脑‘”的问题吗？如果我们回到了D盘并抄下了所有的文件名，我们的工作就结束了。意味着这个程序段已经处理完了应该处理的任务，该结束了。这个动作叫做“跳出”，做出是否进行跳出的判断的程序片断叫做“出口条件”。递归必须要有出口，因为他不断地在呼出自己，一旦没有出口，这个段落将永远执行下去。虽然这不是循环语句，但我们仍然称之为“死循环”。
好了，最后总结一下我们的整个操作：“如果存在没有访问的子文件夹就打开他，没有就抄下当前文件夹下的所有文件名并判断一下是否存在上一层文件夹，如果存在就回到上一层文件夹，反之则跳出”。
递归的定义
这是与Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History