Recursion

递归（Recursion）是一种不停的调用自身的过程。比如下面这个故事就是一个递归的例子

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？「从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？『从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……』」

本文说的递归，讲的是递归函数，也就是一个函数不停的调用自己而形成的。

首先，递归函数都满足两个性质

  1. 有一个 base case。base case 可以理解为可以直接得到结果的一个状态或者说是终止状态。
  2. 每一次函数调用都往 base case 靠拢，否则会形成 infinite loop
    这里我们用阶乘函数 f(n) = n! 来进行说明。对于阶乘函数我们写出的递归函数大致是下面的样子
int fac(int n)
{
  if(n<0) base="" case="" return="" 0;="" if(n<2)="" 1;="" n*fac(n-1);="" 调用="" fac(n-1)，往="" 靠拢="" }<="" pre=""> 


这个函数中前面两个 if 语句组成了 base case。也就是说如果 n<0,那么 n 的阶乘是0，如果 n 是 0 或者 1，那么阶乘是1。这两种情况就组成了阶乘函数的 base case。剩下的 return 语句就是先计算 (n-1) 的阶乘（调用函数 fac(n-1))，然后再乘上 n [n!= n*(n-1)!]，得到最终的结果 n!。


对于递归函数，刚开始的时候难就难在栈状态的理解，首先可以不考虑栈，把递归函数看成一个数学上的递归式，比如上面的阶乘，f(n) = f*f(n-1).那么如果我们想要求 f(n)，首先就需要知道 f(n-1).刚好这就是函数 fac()所解决的问题。对于刚开始学习递归的时候，可以手动模拟代码是怎么跑的，在纸上画出来，方便自己理解。假设我们要求 6！，就会变成下面的状态


1 —> fac(6)


2 —>  6*fac(5)   //6>=2，所以执行最后一句话


3 —> 6(5fac(4)) //5>=2 这里在 5*fac(4)这一层加上括号表示调用 fac(5)的时候，6是被屏蔽掉的，可以理解成”看不见”


4 —> 6(5(4*fac(3))) //4 >=2


5—> 6(5(4(3fac(2)))) //3>=2


6 —> 6(5(4(3(2*fac(1))))) //2>=2


7 —> 6(5(4(3(2*(1)))))      //1 < 2 所以返回1，这里在 1 的外面加上括号表示 1 是一个函数调用过程。


8 —> 6(5(4(32)))      //这里的2表示是调用 fac(2)返回的结果，最里面的 32 是调用 fac(3)时 最后依据 nfac(n-1)的具体化


9—> 6(5(46))    //46 表示的是调用 fac(4) 时执行的最后一句，其中 6 是 fac(4-1) 的结果


10 —> 6(524)     // 5*24 表示的是调用 fac(5) 时执行的最后一句，其中 24 是 fac(5-1) 的结果


11 —> 6120   // 6120 表示的是调用 fac(6) 时执行的组后一句，其中 120 是 fac(6-1) 的结果


12 —> 720 // 调用 fac(6) 返回的结果


每一行中，如果有函数就先计算函数的值，如果没有函数，那么就计算最里面一层括号中的值。对于每一次函数调用都会开辟一块新的栈空间，在相应的栈空间上进行操作， 就算同一个函数，两次不同的调用操作，也会在不同的栈空间上进行操作。这里一开始可以把函数看成一个黑盒子，盒子的输入就是 n， 盒子的输出是 n!,不用去考虑具体的栈空间什么的，这样会比较好一点。


对于阶乘来说，如果传入的参数 n<2 就表示是 base case（<0 的情况是特例需要处理），其它的情况，每次都会调用 fac(n-1)，每次 n 都会减1，这样会往1靠拢，也就是往 base case 靠拢。刚好满足上面两个性质。


在动态规划这篇文章里面，最开始的代码也是用的递归写的，base case 就是前面两个 if 语句判断（base case 一般都是用 if 特判），剩下的就是把其它的状态状态为 base case。比如有名的 Hanoi 塔问题，就可以用来测试自己是否理解了递归。Fibonacci 数列和 Euclid’s GCD 也可以用递归来写，还有一个找零钱问题，也可以用递归来写。很多代码用递归写出来之后会变得很简洁。不过如果递归的层数比较深的话，可能会导致栈溢出的问题。


熟悉递归之后，就还有尾递归的消除，至于怎么消除尾递归（有些语言里面会自带尾递归的消除），这个系列讲的很详细，可以参考参考。

Comments

▲