递归

你是否经常听到身边的程序员说一些高大上的专业术语呢，那递归就一定是其中的一个，这里我们就来讨论下什么是递归。
如果你去查一些专业解释递归的程序书籍，就一定会看到书中经常会使用阶乘来举例。之所以使用阶乘，是因为它能最清楚的表达递归的核心概念。
我们首先解释下阶乘
5的阶乘 ＝ 5! ＝ 5 x 4 x 3 x 2 x 1 = ?
这里因为我们要算的是5！，数字还比较小，所以直接计算是比较快捷的，但是如果要计算100！呢，这个计算的过程是非常机械的
100的阶乘 ＝ 100! = 100 x 99 x 98 x 97 x ...... x 1 = ?
我们应该把机械的工作交给计算机来处理，这样才能有时间发挥自己的创造才能。好了，现在有人要我计算100！是多少，让我用递归的思想来解释给你听整个过程是怎样的。
首先，我不肯能直接把答案给出来，但是如果有人能告诉我99！是多少的话，我就能计算出100！是多少。这一步非常关键
100！＝ 100 x 99!
于是我就去问另一个人99！是多少，暂且叫这个人为man0。显然man0也不可能直接告诉我答案，但是man0说，如果有人能告诉我98！是多少，它就能告诉我99！是多少
99! = 99 x 98!
于是man0找到man1，问他98！是多少。
man1找到man2，问他97！是多少。
......
设想这样下去，直到最后会怎样。manX被问到1！是多少，这个还需要问吗，1！等于1，这时manX就不需要再去问别人了，直接就可以把答案告诉问他问题的那个人。
然后，沿着这条问题链，反方向把答案传递回去，man5把答案告诉man4，man4把答案告诉man3，man3把答案告诉man2，man2把答案告诉man1，man1把答案告诉man0，man0把答案告诉我，我只要把man0告诉我的数值乘以100，就得到了100！。
这就是阶乘运算的整个过程，当我们站在一个全局的角度来看这个整个过程的话，会发现是非常复杂的，但是你在思考递归的时候不应该站在这样的角度，你应该把自己想象成man0或者man1，你只是其中的某一环，不需要去关注全局，这时候问题就会被简化了，仔细细考下。
上面的这个例子里，我们在计算100！的时候，用到了100个人，其中包括“我”、man0、man1......manX，这样来解释这个问题当然没问题，但是和递归的定义稍微有些出入。下面我们换一种方式来解释，不用100个人了，一个人就够。
怎么会原来需要100个人需要解决的问题，一个人就能解决了呢。
你是否看过“盗梦空间”呢，我们把100个人想象层100层梦境，当你想要计算100！的时候，然后你就带着99！是多少这个问题睡去，当第一层梦境醒来的时候，你就知道99！是多少了。第一层梦境会带着98！是多少这个问题睡去。就这样进入一层层的梦境，然后梦境会反方向的一层层醒来，最后当你真的醒来的时候，你就知道100！是多少了。是不是很神奇呢。
或许你会问，递归这个问题直接用乘法连续相乘就行了，何必用递归这么复杂的方法呢。
这里就要说到递归的一个优势，但你使用递归来思考的时候，只需要站在一个局部的角度来思考就行了，不回被整体的复杂度打乱思维。比如说我在计算100！的时候，只需要计算100乘以99！就可以了，具体99！是多少，就交给下一层梦境来解决。
就想上文中说的阶乘问题，我们可以用递归来解决，也可以用迭代（乘法连乘）来解决。迭代是一种非常直接的解决办法，和我们平时的思考方式完全一样，但是递归却不是，需要你去仔细的分析问题。有时候使用递归来解决问题，会让一个复杂的问题变得出奇的简单。