家长怎样给孩子写寄语:递归是什么？要详细解释

阶乘, 斐波那契数列, 快速排序, 还有汉诺塔问题, 都是递归的比较经典的问题, 你要什么例子呢? 你究竟是想学递归还是做什么? 楼上几位讲得是不错的, 唯一遗憾的是都不是用PASCAL语言编的.
下面试一下用PASCAL编一个汉诺塔的程序, 我手头没有书, 想到哪编到哪, 不一定太规范.
有A, B, C三个柱, 在A上N个盘子, 要移到C上去.
用中文建一个程序就是:
begin
移(N-1)个盘子(A到B, 以C为中介); {顶上的盘子}
移1个盘子(A到C); {最底的盘子}
移(N-1)个盘子(B到C, 以A为中介); {第一步移到B的盘子}
end.

对于移一个盘子, 我们只要简单地打印一下就可:
procedure MoveSingle(Origin, Dest: Char);
begin
Writeln(Origin, '==>', Dest);
end;

这一段不编子程序也可.

对于移动多个盘子, 按前面分析的, 可如此实现:
procedure MoveMult(Origin, Dest, Medi: Char, n: Integer);
begin
MoveMult(Origin, Medi, Dest, n-1); {将顶上的盘子移走}
MoveSingle(Origin, Dest); {移最下的盘子}
MoveMult(Medi, Dest, Origin, n-1); {再移顶上的盘子}
end;

注意, 在MoveMult子程序中又调用了MoveMult自身, 这就是所谓的递归.

分析一下, 当有3个盘子时, 为: 先移2个(A==>B), 再移底部的(A==>C), 再把B上的2个移至C.
那么移2个是如何实现的呢? 先移1个(Ori==>Med), 再移1个(Ori==>Dest), 再移一个(Med==>Dest).
移1个时算法如何? 显然又要调用移0个, 而移0个则调用移-1个, 这显然有问题了. 程序一直会进行下去, 直到堆栈溢出为止, 程序死了.
解决的办法是: 当个数为1时直接调用MoveSingle不再递归.
所以递归要有一个终止条件, 否则会无限进行下去. 修改后的递归算法为:

procedure MoveMult(Origin, Dest, Medi: Char, n: Integer);
begin
if n > 1 then {当盘子数大于1时递归}
begin
MoveMult(Origin, Medi, Dest, n-1); {将顶上的盘子移走}
MoveSingle(Origin, Dest); {移最下的盘子}
MoveMult(Medi, Dest, Origin, n-1); {再移顶上的盘子}
end else MoveSingle(Origin, Dest); {当盘子数不大于1时直接移动}
end;

无限递归是递归算法中要注意的, 如果你设计多了, 自然知道什么时候可能会出现无限递归.

完整程序为:
program Hanoi(input, output);
var
n: Integer;

procedure MoveSingle(Origin, Dest: Char);
begin
Writeln(Origin, '==>', Dest);
end;

procedure MoveMult(Origin, Dest, Medi: Char, n: Integer);
begin
if n > 1 then
begin
MoveMult(Origin, Medi, Dest, n-1);
MoveSingle(Origin, Dest);
MoveMult(Medi, Dest, Origin, n-1);
end else MoveSingle(Origin, Dest);
end;

begin
Writeln('Hanoi program');
Write('Input a number: ');
Readln(n);
MoveMult('A', 'C', 'B', n);
end.

没经调试, 如果你要用的话, 自己测试一下.

递归是一种重要的编程技术。该方法用于让一个函数从其内部调用其自身。一个示例就是计算阶乘。0 的阶乘被特别地定义为 1。 更大数的阶乘是通过计算 1 * 2 * ...来求得的，每次增加 1，直至达到要计算其阶乘的那个数。

下面的段落是用文字定义的计算阶乘的一个函数。

“如果这个数小于零，则拒绝接收。如果不是一个整数，则将其向下舍入为相邻的整数。如果这个数为 0，则其阶乘为 1。如果这个数大于 0，则将其与相邻较小的数的阶乘相乘。”

要计算任何大于 0 的数的阶乘，至少需要计算一个其他数的阶乘。用来实现这个功能的函数就是已经位于其中的函数；该函数在执行当前的这个数之前，必须调用它本身来计算相邻的较小数的阶乘。这就是一个递归示例。

递归和迭代（循环）是密切相关的 — 能用递归处理的算法也都可以采用迭代，反之亦然。确定的算法通常可以用几种方法实现，您只需选择最自然贴切的方法，或者您觉得用起来最轻松的一种即可。

显然，这样有可能会出现问题。可以很容易地创建一个递归函数，但该函数不能得到一个确定的结果，并且不能达到一个终点。这样的递归将导致计算机执行一个“无限”循环。下面就是一个示例：在计算阶乘的文字描述中遗漏了第一条规则（对负数的处理） ，并试图计算任何负数的阶乘。这将导致失败，因为按顺序计算 -24 的阶乘时，首先不得不计算 -25 的阶乘；然而这样又不得不计算 -26 的阶乘；如此继续。很明显，这样永远也不会到达一个终止点。

因此在设计递归函数时应特别仔细。如果怀疑其中存在着无限递归的可能，则可以让该函数记录它调用自身的次数。如果该函数调用自身的次数太多，即使您已决定了它应调用多少次，就自动退出。

下面仍然是阶乘函数，这次是用 JScript 代码编写的。

// 计算阶乘的函数。如果传递了
// 无效的数值（例如小于零），
// 将返回 -1，表明发生了错误。若数值有效，
// 把数值转换为最相近的整数，并
// 返回阶乘。
function factorial(aNumber) {
aNumber = Math.floor(aNumber); // 如果这个数不是一个整数，则向下舍入。
if (aNumber < 0) { // 如果这个数小于 0，拒绝接收。
return -1;
}
if (aNumber == 0) { // 如果为 0，则其阶乘为 1。
return 1;
}
else return (aNumber * factorial(aNumber - 1)); // 否则，递归直至完成。

递归通俗的讲就是一个函数在其代码中反复调用自身。你应该知道菲波纳契数列，这个数列的定义是

f(x)=1 (x=1)
f(x)=2 (x=2)
f(x)=f(x-1)+f(x-2) (x>2)
也就是说从第三项开始的每一项的值都等于是前两项之和。这在数学中叫递推数列--高中数学内容。
如果把它变为一个要求第n个菲波纳契数的代码的话，应该如下所示（为了避免语言不通：）我使用伪代码）：

int f(int step)
在这里x为上面所说的x变量，也就是要求的是第x项的值
{
if step=1
{
return 1
}
else if step=2
{
return 2
}
如果求得是第一项和第二项的话，就分别返回1和2，并退出函数

return f(x-1)+f(x-2)
否则的话就返回前面两项的和
}

这里的关键是最后一句。这里函数的返回直又要反过去调用它自身计算前面两项的值，这样就会反复调用，直到x变量在某次调用中变为1和2，返回已知的第一项和第二项的值，在层层返回，最后得出要求的第x项的值

说到本质的话，递归是一段程序的代码反复效用，把程序的参数等变量保存在一个堆栈里，直到到了边界条件以后再层层返回，将堆栈中的数据弹出计算，最后得到结果