“ 一个过程调用自身的方法称为递归。”

递归方法在计算机编程中广泛应用，Stack Overflow的创始人之一Joel Spolsky在《JAVA语言学校的危险性》一文中特别提到了指针和递归对程序员能力的重要程度，不过好像很多软件工程师在编程中不怎么使用递归，甚至有的大公司编程规范直接避免使用递归，之所以会这样主要是能够基于过程自身来定义它的想法会让人不安，能够调用自身的过程怎么会有意义哪？公司规范要求避免使用递归是希望尽量避免代码不可控，因为不是所有的程序员都能很好地使用它，但是作为一个有理想的程序员，必须要认真对待并掌握递归，因为它是构建大型软件系统的根基。

01

—

开端

去年有一部非常火爆的电视剧《开端》，主人公在不停地循环进入相同的公交车场景，这非常像递归的思想，自己不断地在调用自身的过程（公交车剧情），递归之所以让人不安，就在于如果使用不当很容易陷入死循环而无法自拔，这就需要有退出条件，《开端》这部剧退出循环的条件就是还原真相，救下所有的当事人。

递归中的递是进入的意思，归是返回的意思，也就是递归的过程是由进入和返回两个部分组成的，可以想象地下城寻宝的游戏场景，首先是从地面进入，反复进入一层又一层的地穴中寻找宝藏，直到在最深处的地穴中发现了宝藏，就可以原路一层又一层的逐步返回到地面了。进入地穴直到最深处的过程就是“递”，发现了宝藏就是退出条件，返回到地面的过程就是“归”。

02

—

递归方式求阶乘

阶乘在数学上的定义如下：

n!=n*(n-1)*(n-2)...*1

根据上面的公式可以推断出下面两个结论：

1!=1

n!=n*(n-1)!

递归虽然让人不安，但是实际上递归却相当自然明了，我们可以轻易地根据公式写出递归方式计算阶乘的方法，以python为例：

# 递归方式计算n的阶乘, n*(n-1)*(n-2)...*1def factorial(n): if n == 1: return 1 else: return n * factorial(n - 1)

代码几乎就是数学公式的直译，我们以计算6!为例把整个计算过程展开如下图，要计算6!需要逐层递进，直到遇到1!=1这个退出条件，接着就是逐层返回计算结果直到得出最终结果720。

通过上图的形状我们可以看到，计算n!的步骤（时间维度）随着n的规模增加而线性增加，同样的空间（资源消耗）也会随之线性增加，因为解释器要维持层层调用的中间过程所需要的开销。

03

—

迭代方式求阶乘

采用递归方式求阶乘是一种自顶向下的计算方法，还可以采用自底向上的迭代方式计算阶乘，我们把计算阶乘的公式调整一下，先从1开始逐步累乘到n。

n!=1*2*3...*n

# 迭代方式计算n的阶乘，1*2*3*...*ndef factorial(n): product = 1 for i in range(1, n+1): product *= i return product

同样把计算6!的计算过程展开，发现通过迭代方式计算n!的步骤（时间维度）随着n的规模增加而线性增加，但是空间消耗却是固定的，因为计算过程中阶乘的结果都保存在product这个变量中。

04

—

小结

递归思想实际上就是把问题分解为更小规模的问题，每分解一次后的问题就更接近能直接得出结果的基本问题，也就是退出条件。使用递归过程就是设计出问题的分解方式以及找到退出条件。lisp语言支持一种叫“尾递归”的能力，使得在递归形式下也可以进行迭代计算，也就是说所谓的fow、while循环不过是递归形式的语法糖而已，但是并不是所有的语言天然就支持尾递归，也就是说不支持尾递归的语言，即使递归形式上进行的是迭代运算，解释器仍然会维持中间过程的空间开销。