二. 递归原理与构造技巧

递归：

即自己调用自己。将规模较大的问题，化为与之结构相同的规模更小的问题。

尾递归技术：解决了栈溢出及内存不够用的问题

递归的每一次调用都是一个压栈的过程（保持当前函数的参数）

递归的要求：

    ①找相似性（设置相似性）

    ②设置出口

1. 串的翻转

【问题描述】 【源代码】 【JAVA：于航】 public class A {     static String f(String s){         if(s.length()<=1) return s;         return f(s.substring(1)) + s.charAt(0);     }         public static void main(String[] args){         System.out.println(f("abcde"));     }

}

2. 循环改递归

【问题描述】从0到10，不用while和for 【源代码】

【JAVA：于航】

public class A{    static void f(int a, int b){        for(int i=a; i<=b; i++){            System.out.println(i);        }    }       static void g(int a, int b){//使用递归的方法        if(a<b) g(a,b-1);        System.out.println(b);    }       public static void main(String[] args){        //f(1,10);         g(1,10);    }

}

3. 出栈次序

将实际问题——》数学模型化

【问题描述】 X星球特别讲究秩序，所有道路都是单行线。 一个甲壳虫车队，共16辆车，按照编号先后发车，夹在其它车流中，缓缓前行。 路边有个死胡同，只能容一辆车通过，是临时的检查站，如图所示。 X星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。 如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？ 为了方便起见，假设检查站可容纳任意数量的汽车。 显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。 【源代码】 【JAVA：于航】 /*   如果进栈次序为：1 2 3 4 5 。。。   出栈次序有多少种情况？   */ public class A {     // n 个等着进栈，栈中有m个     static int f(int n, int m)     {         if(n==0) return 1;         if(m==0) return f(n-1,1);         return f(n,m-1) + f(n-1, m+1);     }         static int f(int n)     {         return f(n, 0);     }         public static void main(String[] args)     {         for(int i=1; i<17; i++){             System.out.println(i + ": " + f(i));         }     } }

4. 第39级台阶

间接递归：A调B，B又调A

【问题描述】 小明刚刚看完电影《第39级台阶》。离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级! 站在台阶前，他突然又想着一个问题： 如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？ 请你利用计算机的优势，帮助小明寻找答案。 【源代码】

【JAVA：于航】

public class A{    // 奇数步    static long g(int n)    {        if(n==0) return 0;        if(n==1) return 1;        //if(n==2) return 1;               return f(n-1) + f(n-2);    }       // 偶数步    static long f(int n)    {        if(n==0) return 1;        if(n==1) return 0;        //if(n==2) return 1;               return g(n-1) + g(n-2);    }       public static void main(String[] args)    {        System.out.println(f(5));        System.out.println(f(39));    }

}

5. 算式填符号

【问题描述】 匪警请拨110,即使手机欠费也可拨通！ 为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要经常性地进行体力训练和智力训练！ 某批警察叔叔正在进行智力训练： 1 2 3 4 5 6 7 8 9 = 110 请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法；123+4+5+67-89 是另一个可能的答案。 请你利用计算机的优势，帮助警察叔叔快速找到所有答案。 每个答案占一行。形如： 12+34+56+7-8+9 123+4+5+67-89 …… 【源代码】

【JAVA：于航】

public class SuanShi{    //a: 参加计算的元素    //k: 目前考虑的元素下标    //so: 合成好的结果串    //goal: 计算目标    static void f(int[] a, int k, String so, int goal){        if(k==0){            if(a[0] == goal){                System.out.println(a[0]+so);            }            return;        }               f(a,k-1,"+"+a[k]+so, goal-a[k]);//即最后一个元素9开始考虑

        f(a,k-1,"-"+a[k]+so, goal+a[k]);

        int old = a[k-1];         a[k-1] = Integer.parseInt( "" + a[k-1] + a[k]);//什么符号都不加，后两位数合成一个数，拼成串，再转为Integer         f(a,k-1, so,goal);//此处不变，因为没有符号变化         a[k-1] = old;//一定要回溯：若归并后，发生错误，无法继续运行，就必须要回溯（恢复）     }         public static void main(String[] args){         int[] a = {1,2,3,4,5,6,7,8,9};              f(a,8,"",110);     }

}

6. 找钱问题

【问题描述】 公园票价为5角。假设每位游客只持有两种币值的货币：5角、1元。 再假设持有5角的有m人，持有1元的有n人。 由于特殊情况，开始的时候，售票员没有零钱可找。 我们想知道这m+n名游客以什么样的顺序购票则可以顺利完成购票过程。 显然，m < n的时候，无论如何都不能完成； m>=n的时候，有些情况也不行。比如，第一个购票的乘客就持有1元。 请计算出这m+n名游客所有可能顺利完成购票的不同情况的组合数目。 注意：只关心5角和1元交替出现的次序的不同排列，持有同样币值的两名游客交换位置并不算做一种新的情况来计数。 【源代码】 【JAVA：于航】 //考虑最后一个人 public class ZhaoQian1 {     //m: 持有5角的     //n: 持有1元的     static int f(int m, int n){         if(m<n) return 0;//当m<n时，无解         if(m==1) return 1;//则持有5角的人只能排到队头         if(n==0) return 1;//即5 5 5 5 5 5。。。的情况            

        return f(m-1,n) + f(m,n-1);

        //f(m-1,n)即：最后一个人持五角，则其余还有m-1个人持有五角

        //f(m,n-1)即：最后一个人持有一元，则其余还有n-1个人持有一元

    }         public static void main(String[] args){         System.out.println(f(2,2));         System.out.println(f(3,2));         System.out.println(f(5,3));     } } //考虑第一个人 public class ZhaoQian2 {     //m: 持有5角的     //n: 持有1元的     //t: 售票员手里有多少个5角的     static int f(int m, int n, int t){

        if(m+t<n) return 0; 

        if(m==0) return 1;

        if(n==0) return 1; 

        //相似性的设置：

        int r = f(m-1,n,t+1);//假设第一个人手里是五角的，则售票员手中的五角多了一个

        if(t>0) r += f(m,n-1,t-1);//假设第一个人手里是一元的，此时有解，售票员手中的五角少了一个

        return r;     }         public static void main(String[] args){         System.out.println(f(2,2,0));         System.out.println(f(3,2,0));         System.out.println(f(5,3,0));     } }

7. 振兴中华

【问题描述】 小明参加了学校的趣味运动会，其中的一个项目是：跳格子。 地上画着一些格子，每个格子里写一个字，如下所示：（也可参见下图） 从我做起振 我做起振兴 做起振兴中 起振兴中华 比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。 要求跳过的路线刚好构成“从我做起振兴中华”这句话。 请你帮助小明算一算他一共有多少种可能的跳跃路线呢？ 【源代码】

【JAVA：于航】

public class A{    static int f(int m, int n)//从某个坐标位置一直走，一共多少走法？    {        if(m==1 || n==1) return 1;//出口：最下或最右时               return f(m-1,n) + f(m,n-1);//即往右走+往下走    }       public static void main(String[] args)    {        System.out.println(f(5,4));        //System.out.println(f(3,2));    }}