经典递归问题（1）

组合问题递归解

在n个球中，任意取出m个（不放回），求有多少种不同取法。

思路：从题目上看，这问题对于递归来说似乎没有突破口。首先，我们可以确认int f(int n,int m)，指的是从n个球取出m个球，f这个函数返回的是从n个球取出m个球的取法的种树。我们可以想象一个红色的球，其他都是白球。那么我们要么要取这个红球，要么不取这个红球。如果要取这个红球，则我们已经确定m个球其中一个球是红球，则需要从n-1球(因为红球确定已被取出)中取出m-1个球即可，即f(n-1,m-1)。如果不取这个红球，则需要从n-1球(因为红球已确定不被取出)中取出m个球即可，即f(n-1,m)。则从n个球中取出m个红球的取法种数就是取出红球数量和不取出红球数量之和，即f(n-1,m-1)+f(n-1,m)。
代码如下：

public class 递归4_取球 {
    public static void main(String[] args){
        System.out.println(f(6,3));  //从6个球中取3个球
    }
    public static int f(int n,int m){
        if(m>n)
            return 0;
        if(m==0)  //如果取到最后，只有一种取法
            return 1;
        if(m==n)    //如果要取的球跟总球数相同，只有一种取法
            return 1;
        return f(n-1,m-1)+f(n-1,m);
    }
}

全排列问题

求n个元素的全排列。

思路：可以把每个元素先放在开始这个位置，把后面元素全排列。
由于我们要交换字符，所以要把元素遍历，并且要有一个待交换点k作为起始地址，在递归之前，将待交换点跟遍历的位置交换，即试探。递归后，把字符交换回来。以便，后面的交换点遍历交换的时候不会出错。
代码如下：

public class 递归5_全排列 {
    public static void main(String[] args){
        char []data="ABC".toCharArray();
        f(data,0);
    }
    //k：当前的交换位置（关注点），与其后的元素交换
    public static void f(char[] data,int k){
        // 出口
        if(k==data.length){
            for (int j=0;j<data.length;j++){
                System.out.print(data[j]+" ");
            }
            System.out.println();
        }
        for(int i=k;i<data.length;i++){
            {
                char t=data[k];
                data[k]=data[i];   //试探
                data[i]=t;
            }
            f(data,k+1);
            {
                char t=data[k];
                data[k]=data[i];   //回溯（一定不要忘记）
                data[i]=t;
            }
        }
    }
}

最大公共子序列问题

求出字符串中最大公共子序列
比如（abc abd bdf ...... 都是字符串abcdef的子序列）

思路：设有两个字符串s1和s2，分别取两个字符串中的第一个字符ch1，ch2。如果ch1==ch2，那么只要求ch1和ch2中剩下的字符串中最大公共子序列的长度，再+1就是要求的结果。如果ch1!=ch2，那么把s1中除了第一个字符以外的剩下的字符和整个s2进行比较，得到最大公共子序列len1，再把s2中除了第一个字符以外的剩下的字符和整个s1比较，得到最大公共子序列len2，取len1和len2的最大值。
代码如下：

public class 递归6_最大公共子序列 {
    public static void main(String[] args){
        System.out.println(f("abc","xback"));
    }
    public static int f(String s1,String s2){
        if(s1.length()==0||s2.length()==0)
            return 0;
        if(s1.charAt(0)==s2.charAt(0))
            return f(s1.substring(1),s2.substring(1))+1;
        else
            return Math.max(f(s1.substring(1),s2),f(s1,s2.substring(1))) ;
    }
}