胡思乱想说递归-上

原来在学习数据结构和算法的时候，学习到递归，当时觉得递归就是一种自己调用自己的方法嘛，只要控制好递归的结束条件就可以了。可是在工作之后才发现，对于很多问题，采用递归的思想可以大大降低实现的难度（暂时先不考虑效率），所以决定好好的研究一下递归。

什么是递归

递归方法对应于数学上的归纳法，把一个想要解决的问题转化为解决他的子问题，子问题又可以继续转化为子问题的子问题，这些子问题与原问题有着相同的结构或者说有着相同的模型。当然了这些子问题并不是可以无限分解的，使的问题不能继续分解下去的条件被我们称为递归结束条件。

递归从大的方面，分为两个步骤：递和归。把问题分解为子问题的过程属于"递"，到达了递归结束条件，使得子问题出栈的过程属于"归"

一般的递归都分为：

1. 结束条件
2. 直接求解表达式。就是在到达结束条件的时候，我们可以直接用来求解的表达式
3. 步进表达式和归纳项。之所以把这两个合为一个，是因为这两个经常会一起用。步进表达式是可以使得递归可以继续向下分解的表达式。归纳项是只在这一次递归过程中，我们对于该子问题的处理逻辑。

一般递归的形式如下：

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);
}

通过上面的例子，我们可以总结出来可以使用递归处理的问题的一些共同特征：

1. 可以把该问题逐步分解为一个个的小问题，而且这些小问题与原问题有相同的结构或者说表述
2. 存在某种条件，使得问题不能继续分解，并且在该条件下问题可以得到非常容易的解决。

只要满足着两个条件，就可以采用递归的办法来解决

接下来举一个比较复杂的问题：

有这么一个数据，全部由数字构成，比如字符串"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;
        }
    }
}

上半部分就说到这里。下一部分说一下 递归，迭代和循环，以及尾递归的问题