递归

指通过反复使用相同的规则来生成无穷的短语或句子的语法手段。原为数学概念，后由转换·生成语法学派引入语言学研究。如我们描写像“爷爷的帽子”、“爷爷的爷爷的帽子”、“爷爷的爷爷的爷爷的帽子”等一系列结构，按一般方法往往需要无限多的句法规则，但如果使用递归手段，则只须反复用以下两条规则： AP→MPA,MP→M (MP)(其中A代表名词“帽子”，M代表修饰语“爷爷”，AP代表整个短语)，就能描写全部这类结构。

递归digui

一个过程直接或间接调用它本身，则称该过程是递归的.例如，求阶乘的过程可视之为递归过程.
定义：正整数n的阶乘为f(n).
f (n)=n!
f (n-1) = (n-1)!
则f (n) =nf (n-1)
从上式可知，欲求f (n)可先求f (n-1)；欲求f (n-1)又可先求f (n-2)；…，就象剥一颗圆白菜，从外向里一层层剥下来，最后到0的阶乘，f (0)=1，到达了递归的边界，然后再用f (n) =nf (n-1)，从里向外倒推回去得到f (n)的值.
这里，f (n)是计算阶乘的过程，n是该过程的一个参数，计算f (n)是以n为参数调用过程f (n)；而欲求f (n)，先要以n-1为参数调用同一过程f (n-1)，这就是过程直接调用过程自己，这种自己调用自己的算法称之为递归算法.
典型的递归算法是著名的哈诺塔问题：古代印度僧人想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去，移动过程中恪守这样的规则：共有三根柱子，每次只允许移动一个盘，且大盘不得落在小盘上.按照这个规则每秒钟移动一个盘，则需5800多亿年才能完成任务，
这个问题，如果不用递归算法是解不出来的.
先将盘子自小到大以1,2，…，64编号，将三根柱子分别标以a,b和c，先看两个盘子的搬移过程.开始时，两盘2在下，1在上套在a柱上.第一步将1从a移至b；第二步将2从a移至c；第三步再将1从b移至c.我们将这一过程描述为
MOVE (2,a,b,c)
意为：将2个盘子(由2号盘与1号盘组成)从a柱经b柱移至c柱.这一过程分三步完成：
MOVE 1:a→b 将1由a移至b
MOVE 2:a→c 将2由a移至c
MOVE 1:b→c 将1由b移至c
以上算法描述了两个盘子的移动过程.如果是n个盘子(n>2)，则把MOVE (n,a,b,c)移动过程想像为上述移动两个盘的过程.为此，将上面的n-1个盘“捆”在一起当成一个小盘.也分三步.
　MOVE (n-1,a,c,b) 将n-1个盘从a (经c)移至b
　MOVE n:a→c 将n号盘由a移至c
　MOVE (n-1,b,a,c) 将n-1个盘从b(经a)移至c
当n>2时，上述三步只有第二步为直接步骤，其它两步还要进一步分解.但是却把移动n个盘子的过程简化为移动n-1个盘子的问题.接下去再将移动n-1个盘子的问题简化为移动n-2个盘子的问题.这样每次减少一个盘子，直到最后只剩下一个盘子为止.这种分解动作，用到过程自己调用自己，是典型的递归算法.