辅导资料 历年递归试题

一、反转串

代码如下：

/*
 * 构造递归的要诀：
 * 1.找到相似性
 * 2.定义出口
 */
package sf_1;
public class Main {
    public static String reverseString(String x){
        if(x==null||x.length()<2)
            return x;
        return   reverseString( x.substring(1))+x.charAt(0);
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.print(reverseString("abcd"));
    }
}

运行截图：

二、杨辉三角形

代码如下;

package sf_2;

public class Main {
    /*
     * 1
     * 1 1
     * 1 2 1
     * 1 3 3 1
     * 1 4 6 4 1
     * 1 5 10 10 5 1
     */
    public static int f(int m,int n){
        if(m==0)
            return 1;
        if(n==0||n==m)
            return 1;
        return f(m-1,n)+f(m-1,n-1);
    }
    public static void main(String[] args) {
        int level=5;
        for(int i=0;i<=level;i++)
            System.out.print(f(level,i)+" ");
                System.out.println();
}

}

运行截图：

三、

代码如下：

package sf_3;
public class Main {
    /*
     * m个A，n个B，组成多少排列
     */
    public static int f(int m,int n){
        if(m==0||n==0)
            /*
             * 它的意思是当n=0时，此时仅仅剩下a，则只有一种情况；同理，
             *           当m=0时，此时仅仅剩下b，则只有一种情况
             */
            return 1;
        return f(m-1,n)+f(m,n-1);
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.print(f(3,2));
    }
}

运行结果：

四、

代码如下：

package sf_4;
public class B {
    /*
     * 对于n进行加法划分
     * 存一个数组a缓冲;当前位置k;
     */
    public static void f(int n,int a[],int k){
         /*
         * 递归出口
         */
        if(n<=0){
            for(int j=0;j<k;j++){
                if(j==k-1)
                    System.out.print(a[j]);
                else
                    System.out.print(a[j]+"+");
            }
            System.out.println();
            return;
        }
        for(int i=n;i>=1;i--){
            /*
             * 应当保证前一个比后一个数大
             */
            if(k>0&&i>a[k-1])
                continue;
            a[k]=i;
            f(n-i,a,k+1);
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[]=new int[1000];
        f(6,a,0);
    }
}

五、

代码如下：

package sf_5;
public class B {
    /*
     * err_sum表示有错的和
     * a：明细,只是传入 并不修改
     * k：当前处理的位置
     * cur_sum：前边的元素的累加和
     * b:记录取舍
     */
    public static void g(int err_sum,int a[],int k,int cur_sum,boolean[] b){
        //已经大于err_sum  不满足条件
        if(cur_sum>err_sum) return;

        //问题得到了一个解，哪些项没有选
        if(cur_sum==err_sum){
            for(int i=0;i<b.length;i++)
                if(b[i]==false)
                    System.out.print(i+" ");
                System.out.println();
                return;

        }

        //当前项已经到尾了
        if(k>=a.length) return;

        b[k]=false;
        g(err_sum,a,k+1,cur_sum,b);

        /*
         * 将其设置为了true 
         * 在回溯的时候应当设置为false
         */
        b[k]=true;;
        cur_sum+=a[k];//选中了第k个元素
        g(err_sum,a,k+1,cur_sum,b);
        b[k]=false; 
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int sum=6;//总和是6
        int[] a={3,2,4,3,1};
        //表示a的对应项是否选取
        boolean[] b=new boolean[a.length];
        g(6,a,0,0,b);
    }
}

运行截图：