第一百二十四章 递归

    递归是计算机应用里的一门学问。递归函数，学过数学的都知道递归是数学里的一大难点，而到了计算机里更是难以接受。

    在编程语言中，函数直接或间接调用函数本身，则该函数称为递归函数。递归函数不能定义为内联函数。

    在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。中文名递归函数。

    连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的[1]。

    古典递归函数，是一种定义在自然数集合上的函数，它的未知值往往要通过有限次运算回归到已知值来求出，故称为“递归”。它是古典递归函数论的研究对象。

    在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数，它是在某种直觉意义上是“可计算的“。事实上，在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。递归函数有关于原始递归函数，并且它们的归纳定义(见下)建造在原始递归函数之上。但是，不是所有递归函数都是原始递归函数—最著名的这种函数是阿克曼函数。

    其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。

    是所谓能行可计算函数，另一类是非能行可计算的函数。这前一种函数无论在理论上或在实际上都是非常重要的，因此人们便试图给它们以精确的数学刻画。递归函数便是许多这种刻画中的一种?。

    我们所考虑的关于递归函数的例子函数都是从自然数到自然数的函数。这样便于理解和认知。递归算法一般用于解决三类问题：

    首先，数据的定义是按递归定义的。

    其次，问题解法按递归算法实现。

    在这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。

    最后数据的结构形式是按递归定义的。

    比如如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。

    当然，对递归的应用也存在不可避免的缺点：

    递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

    递归典型问题：梵塔问题（汉诺塔问题）

    递归函数的学问说大不大，说小也不小。内行人看门道，外行人看热闹，想要真正的了解和掌握，还要更深入的学习和认知。