原来在学习数据结构和算法的时候，学习到递归，当时觉得递归就是一种自己调用自己的方法嘛，只要控制好递归的结束条件就可以了。可是在工作之后才发现，对于很多问题，采用递归的思想可以大大降低实现的难度（暂时先不考虑效率），所以决定好好的研究一下递归。
什么是递归
递归方法对应于数学上的归纳法，把一个想要解决的问题转化为解决他的子问题，子问题又可以继续转化为子问题的子问题，这些子问题与原问题有着相同的结构或者说有着相同的模型。当然了这些子问题并不是可以无限分解的，使的问题不能继续分解下去的条件被我们称为递归结束条件。
递归从大的方面，分为两个步骤：递和归。把问题分解为子问题的过程属于"递"，到达了递归结束条件，使得子问题出栈的过程属于"归"
一般的递归都分为：
- 结束条件
- 直接求解表达式。就是在到达结束条件的时候，我们可以直接用来求解的表达式
- 步进表达式和归纳项。之所以把这两个合为一个，是因为这两个经常会一起用。步进表达式是可以使得递归可以继续向下分解的表达式。归纳项是只在这一次递归过程中，我们对于该子问题的处理逻辑。
一般递归的形式如下：
public void fun(factor){
if(end){
//end就是递归的结束条件
//directResolve()就是直接求解表达式，在很多时候我们仅仅是想要终止递归，并不需要子问题返回值，所以这时候可以没有直接求解表达式，直接return
directResolve();
}else{
//这就是归纳项，对于本次递归我们要处理的逻辑
doSomething(factor);
//这个就是不进表达式，通过不断改变factor的值来使递归向着终止条件靠近
factor=move(factor);
//调用自身，实现递归
fun(factor);
}
}
递归的例子
举个最简单的例子，那就不得不说求N的阶乘
public static int factorial(int n){
//n就是步进因子
if(n == 1){
//n==1是递归终止条件
//return 1是直接求解表达式
return 1;
}
//以下这一句n-1是步进表达式
//n*factorial(n-1)是归纳项
//这就是为什么上面说归纳项和步进表达式经常在一起
return n * factorial(n - 1);
}
通过上面的例子，我们可以总结出来可以使用递归处理的问题的一些共同特征：
- 可以把该问题逐步分解为一个个的小问题，而且这些小问题与原问题有相同的结构或者说表述
- 存在某种条件，使得问题不能继续分解，并且在该条件下问题可以得到非常容易的解决。
只要满足着两个条件，就可以采用递归的办法来解决
接下来举一个比较复杂的问题：
有这么一个数据，全部由数字构成，比如字符串"123456",或者整形123456，甚至可以是数组[1,2,3,4,5,6]（为了演示的方便，我把他当做字符串）。任意删除其中的T位，比如删除其中的两位，剩余的数字按照原来的顺序排列，求一个算法，使得删除之后的数字的值最小。
比如"123456",可以删除3和6,得到"1245",也可以删除1和2，得到"3456"，我们要求得删除之后最小的那个数，这里为"1234"。
就这样一个问题，网上有很多的解法，这里我说一下递归的解法。
这个问题可以概括为：一个N位数字，删除T位，剩余的按原来的顺序求值，求剩余数字的最小值。
按照递归的思路，求N位数字，删除T位，可以先求出N-1位数字删除T-1位，求出最小值，然后N-2位删除T-2位，求出最小值，一次类推，当N=0或者T=0的时候结束递归。
按照上面思路给出代码:
public static String findMin(String value, int T){
final int N = value.lenght();
if(N<=T||N<=0||T<=0){
//这是递归终止条件
return value;
}
String result = value;
for(int i = 0;i<N;i++){
//一次删除value中的每一位，其余的位数按原来的顺序组合，得到一个N-1位的数字，然后递归求出这N-1位删除T-1的最小值
String tmp = value.subString(0,i)+value.subString(i+1,N);
String temResult = findMin(tmp,T-1);
if(Integer.valueOf(result)>Integer.valueOf(tmpResult)){
result = tmpResult;
}
}
return result;
}
这个的思想是每次递归都找到最小的，当T减小到0的时候就正好可以求出删除T位的时候最小数字。
比如，当value为"312456",T为2时，返回"1245"
这也是递归和循环结合使用的一个比较不错的例子
有一个二分查找法，也是递归比较经典的使用。
题目就不说了，现在来说一下它的解法思想：把已经排序好的要查找的数字二分，比较中间数字与目标的大小，如果中间数字比目标大，则说明要查找的在前一部分，然后继续对前一部分使用相同的办法，下面来写一下方法。
//假设data已经排序过了,如果找到了，就返回该key第一次出现的位置，否则返回-1
public static int binarySearch(int[] data, int start, int end, int key){
int mid = (start+end)/2;
final int N = data.length;
if(end<=start){
//递归终止条件
if(data[start] == key){
return mid;
}else{
return -1;
}
}
//归纳项
if(data[mid]>key){
return binarySearch(data,start,mid,key);
}else if(data[mid]<key){
return binarySearch(data,mid+1,end,key);
}else{
return mid;
}
}
}
上半部分就说到这里。下一部分说一下 递归，迭代和循环，以及尾递归的问题
