递归

在不同的文献中，“递归”一词有不同的涵义。

有一些文献中，“递归”等同于原始递归。本书采取这种用法。在另一些文献中，“递归”的涵义要广一些，是包括原始递归在内的一类函数运算的总称。其共同的基本思想是：①将定义域中的元素排成良序，②给出自变量取极限点的值时函数值的计算方法，③给出将每个后继元上函数值的计算归约为其一个或多个前趋上的函数值的方法。

在这个意义下，除原始递归以外，递归运算中还包括多步递归、多重递归、联立递归、嵌套递归，等等。

多步递归 在计算h(x，…，x，y+1)时要用到h(x，…，x，0)，h(x，…，x，1)，…，h(x，…，x，y)中的可能不止一个值，例如斐波那契(Fibonacci)级数的定义

就是多步递归。

多重递归 同时对多个变元作递归。例如：

联立递归 一种同时产生多个函数的方法。例如：

嵌套递归 在递归的过程中h本身作一次或多次复合。例如：

以上几种递归运算原则上都可以归约为原始递归。

另外，还有一些文献在更广的意义下使用递归一词，例如将阿克曼函数的定义方法乃至超穷递归也包括在内。