递归 (计算机科学)

维基百科，自由的百科全书

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

使用递归解决问题，思路清晰，代码少。

河内塔问题，是已知的，在编程方面只能用递归解决的问题。

其它可能用到递归解决的问题有菲波纳契数列。

以下为求河内塔问题的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
      结束;

[编辑] 定義的遞歸

遞歸的「定義」可视为一种幽默：

遞歸

——參見「遞歸」。