??工欲善其事，必先利其器。
递归-Recursion递归是一种应用非常广泛的算法（或者编程技巧）。
后续一些复杂的算法和数据结构都用到了递归，所以，搞懂递归非常重要。
递归例子周末你在排队买东西，队伍太长了，于是你想知道自己排在第几位，但是你又不想自己数，于是你问前面的人是第几位，但是他也不知道，于是一个一个往前询问，到了第一个人时，他知道自己是第一个，于是告诉后面的人，后面的人加一就是他的位数，一层层传递到你这边来，你也就知道自己是第几位了（现实中不太可能，这里举个例子）
这就是一个非常标准的递归求解问题的分解过程，去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子，我们用递推公式将它表示出来就是这样的：
f(n)=f(n-1)+1其中，f(1)=1
f(n)表示你想知道自己在哪一位，f(n-1)表示前面一位所在的位数，f(1)=1表示第一位的人知道自己在第一位。有了这个递推公式，我们就可以很轻松地将它改为递归代码，如下：
intf(intn){if(n==1)return1;returnf(n-1)+1;}递归需要满足的三个条件
刚才的例子就是一个典型的递归，那么满足什么条件的问题可以用递归来解决呢？
一个问题的解可以分解为几个子问题的解何为子问题？子问题就是数据规模更小的问题。比如，前面讲的排队的例子，你要知道，“自己在哪一位”的问题，可以分解为“前一位的人在哪一位”这样一个子问题。
这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样比如排队那个例子，你求解“自己在哪一位”的思路，和前面一位人求解“自己在哪一位”的思路，是一模一样的。
存在递归终止条件把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。还是排队的例子，第一位的人不需要再继续询问任何人，就知道自己在哪一位，也就是f(1)=1，这就是递归的终止条件。
如何编写递归代码呢？刚刚说了很多递归有关的内容，那么在实际运用中如何去写一个递归呢？
写递归代码最关键就是：
找到规律写出通用公式找到截止条件学习算法和数据结构，需要多练多写，通过下面几个例子说明下递归。
1.Fibonacci数列关于递归，有些人可以想到的是斐波那契数列。
什么是斐波那契数列呢？
0,1,1,2,3,5,8,13...总之，就是第N(N2)个数是等于第（N-1）数和第（N-2）数的和。
05_递归-斐波那契数列那么通过上面关键分析：
首先找到规律
从第三个数开始，每个数的值都是它前两项的和。
通用公式
f(n)=f(n-1)+f(n-2)
截止条件
当n小于等于2时，就结束递归。
通过上面的综合来看，写出的代码如下：
publicstaticintFibonacci(intn){if(n==1)return0;if(n==2)return1;returnFibonacci(n-1)+Fibonacci(n-2);}2.Factorial阶乘
数学中常见的阶乘，也是可以使用递归进行计算。
阶乘：n!=1*2*···*(n-1)*n
首先找到规律
求解阶乘，将从1到n的数字相互进行乘法运算
通用公式
f(n)=n*f(n-1)
截止条件
当n等于1时，就结束递归。
代码如下：
publicstaticintFactorial(intn){if(n==1)return1;returnn*Factorial(n-1);}总结
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲截止条件，最后将递推公式和终止条件翻译成代码。
学习递归过程中，如果面对的是一个问题要分解成多个子问题的情况下，递归代码就没有那么好理解了。
人脑几乎没办法把整个“递”和“归”的过程一步一步都想清楚，而计算机擅长做重复的事情，所以递归正合它的胃口。而我们人脑更喜欢平铺直叙的思维方式。当我们看到递归时，我们总想把递归平铺展开，脑子里就会循环，一层一层往下调，然后再一层一层返回，试图想搞清楚计算机每一步都是怎么执行的，这样就很容易被绕进去。
对于递归代码，这种试图想清楚整个递归过程的做法，实际上是进入了一个思维误区。很多时候，我们理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍。那正确的思维方式应该是怎样的呢？
如果一个问题A可以分解为若干子问题B、C、D，你可以假设子问题B、C、D已经解决，在此基础上思考如何解决问题A。而且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。
因此，编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
而且在进行递归计算时，需要注意下面几点：
递归代码要警惕堆栈溢出递归代码要警惕重复计算对于递归中的堆栈溢出，则可以通过判断进行最大数据处理拦截，比如设置数据规模大于时，则抛出错误即可；但是这种方式并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。所以，如果最大深度比较小，比如10、50，就可以用这种方法，否则这种方法并不是很实用。
而针对于重复计算问题，其实可以在后续算法与数据结构中的散列表来进行操作和处理，使用散列表保存已经计算过的数据，当递归调用到f(k)时，则先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，就可以避免重复计算问题。
递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以在实际使用中，需要根据需求来选定方式，可以将递归改为循环来处理。
本文作者：SpiritLing（