递归是什么？要详细解释

阶乘, 斐波那契数列, 快速排序, 还有汉诺塔问题, 都是递归的比较经典的问题, 你要什么例子呢? 你究竟是想学递归还是做什么? 楼上几位讲得是不错的, 唯一遗憾的是都不是用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), 再