【再谈递归】递归理解了，该如何去写程序

如果你理解了递归，那么你就成功了一半

递归分为两个部分，“递”和“归” 递归递归先递再归。

可能很多同学对递归还不了解，那我在这里来说一说：何为递归。

何为递归？

递归指的是在函数（方法）的定义中使用函数（方法）自身的方法。 举个例子： 从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有 …

所以，递归的特点之一：函数自己调用自己

不过像上述“老和尚讲故事”的案例，通常称为 单程递归 （这个概念来自于 刘慈欣的《星际战争》第11章），所谓单程递归，就是没有返回的递归，也就是只有递，没有归。

如何理解递归

众所周知，在一个函数（方法）被调用时，会开辟一个新的空间，而在递归时，函数调用自己，也会新开一个空间，而每当新开的空间内函数调用完毕时，会将值返回给上一个空间，无限重复调用，直到找到基准为止（我对于内存空间的研究有限，可能说的不太对，不过也是为了便于大家的理解）

用递归写个斐波那契，大家都很好想像，不过用递归来写排序呢？快速排序可能还好点，如果是归并，给人的感觉就有点抽象了

快速排序

归并排序

要是每一次自行模拟的时候，都带进去，人不累死，脑子都得晕死。

所以，如何用好递归？

用好递归

前面说到，递归是有返回值的，所以，我们在写递归的时候，不妨设它是一个已经写好了的函数，我们只需要知道他返回的结果是多少不就可以了吗。

下面以斐波那契数列为例（万能的斐波那契，赐予我力量吧！）

调用fib(n-1)+fib(n-2)时，我们如果带进去算，会陷入循环中，循环到底回来的时候，还要记录返回值，对于计算机来说，有手就行，但对于我们普通人来说，特别绕（特别是当输入的n很大时），我们不妨假设已经知道它的返回值来运行，再进行调试，这样的话，便不会陷入头晕目眩的恶性循环。