递归

Jun 30, 2018

递归（recursion）是数学中处理问题的一种常用方法，在计算机科学中指的是一种通过重复将问题分解为同类的子问题而解决问题的方法。

换句话说，在处理分治问题上采用递归是一种很简单的方法，其强大描述能力，可以把无限过程表达在有限语句中。

以下讨论的均是线性过程，都使用数学公式描述，而非任何一种编程语言

递归过程和计算过程

阶乘是一种典型的递归过程，从递归的定义来说反复的调用同一种函数解决问题，就是一种递归。

计算机不能处理无限的过程，所以递归必须要有一个条件终止当前计算，称为终止条件，这里阶乘的终止条件就是 n=0 。

要实现递归的编程总体来说有两种方法，一种的循环、另一种是递归。在某种意义上来说递归过程是可以完全转化成循环过程，反之不一定成立。

把阶乘公式转化成具体的演化过程，以 f(6) 为例子。

从演化过程可以看出的计算步骤可以看出一种很明显是，先展开后收缩的过程。

展开阶段是一种计算的构造过程，收缩阶段是实际的计算过程，完整的完成一次计算需要 12 个计算步骤，这种形状的计算称为 递归计算过程。

执行递归计算过程，需要维护好这一轨迹，缺少了任一步骤，此次计算都会失败。所以说在计算机当中执行这种递归过程中，需要使用额外的资源来存储执行轨迹。

以上的递归计算过程，本次的计算是依赖于上次计算的轨迹。一种优化方案就是把每次计算都做成独立的一部分，不依赖于执行轨迹，要做的就是用一个变量去存储本次的计算结果。

这种曲线形状的计算 迭代计算过程。相比于递归计算过程把轨迹信息存储于每次的函数调用当中，所需要的计算步骤和长度成线性增长关系。

描述一个过程是否为递归，自需要观察是否调用的自身，如果就是 递归过程。实现递归过程有两种计算过程：

需要理解清楚的是递归过程和计算过程的关系，基于迭代计算过程，现代编程语言会对其进行优化，采用 尾递归 语法，就可以使用常规的过程调用机制来描述迭代计算过程。

尾递归是一种解释器的优化方案，依赖于尾调用和迭代计算过程。

对于一般的函数调用而言，在调用的开始需要把当前的地址及其变量入栈，在被调用函数执行完成以后，把调用前入栈的内容弹出继续执行。当函数调用的层级非常多，函数的调用栈会消耗不少的内存，也有可能会产生栈溢出。

尾调用就是优化了返回函数的调用栈，结合递归计算过程，可以把 O(n) 空间优化成 O(1)，极大的节省资源的浪费，对于需要大量的递归计算来说十分有用。

绝大多数的函数式编程语言尾递归优化都是标准，必须要实现的。
但是有一些命令式编程语言是不支持尾递归优化的比如 Python。