第二节：递归原理
递归的重点在于：①找相似性②设置出口
第一题：振兴中华
小明参加了学校的趣味运动会，其中的一个项目是：跳格子。 地上画着一些格子，每个格子里写一个字，如下所示：（也可参见下图） 从我做起振 我做起振兴 做起振兴中 起振兴中华 比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。 要求跳过的路线刚好构成“从我做起振兴中华”这句话。 请你帮助小明算一算他一共有多少种可能的跳跃路线呢？
思路：如上图建立平面直角坐标系，则从的坐标为（5，4），华的坐标为（1，1），根据条件以及图分析出，要想走过的路线构成“从我做起振兴中华”，则必须只能向右和向下走，直到走到（1，1）为止。根据之前说的递归的两个重点，我们先找相似性，相似性就在于自“从”字开始，只能向右和向下移动，自（5，4）向右走，方法有p中，自（5，4）往下走方法有q种，则总方法数应当为p+q，因此组成完整话语的方法是f(x-1,y)+f(x,y-1)；出口则应该设置为当x=1 or y=1，因为此时，从这点到达（1，1）的方法仅一种，即向下（当x=1）,向右（y=1）;
代码：
public class Main {
public static void main(String[] args) {
System.out.println(f(5,4));
}
static int f(int x,int y){
if(x==1||y==1) return 1;
return f(x-1,y)+f(x,y-1);
}
}第二题：出栈顺序
X星球特别讲究秩序，所有道路都是单行线。 一个甲壳虫车队，共16辆车，按照编号先后发车，夹在其它车流中，缓缓前行。 路边有个死胡同，只能容一辆车通过，是临时的检查站，如图所示。 X星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。 如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？ 为了方便起见，假设检查站可容纳任意数量的汽车。 显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。
思路：首先通过题目描述可以知道，每辆车都要进检查站（这个条件要注意），设未进入检查站的队列为a，检查站内的车队为b，可以分为以下三种情况：①当a中没有车了，那么出站后车的顺序是已经确定的了；②当b中没车时，a要向b中进车；③当a，b中都有车时可以分两种情况即a继续向b中进车以及b出车，因此代码如下：
public class Main {
public static void main(String[] args) {
for(int i=1;i<=16;++i)
System.out.println(i+":"+f(i,0));
}
static int f(int a,int b){
if(a==0) return 1;
if(b==0) return f(a-1,1);
return f(a-1,b+1)+f(a,b-1);
}
}
第三题：算式填符号
匪警请拨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 ......
这个题没大看懂，先把正确代码贴上记录，日后再看：
//a：字符串
//k:当前位置的下标
//so：当前字符串
//goal：目标数字
public class Main {
public static void main(String[] args) {
int []a = {1,2,3,4,5,6,7,8,9};
f(a,8,"",110);
}
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]); //当为＋时
f(a,k-1,"-"+a[k]+so,goal+a[k]); //当为－时
int old = a[k-1]; //当递归结束后需要把之前的a[k-1]还原
a[k-1] = Integer.parseInt(""+a[k-1]+a[k]);//将两个字符拼接
f(a,k-1,so,goal);
a[k-1]=old;
}
}第四题：第39级台阶
小明刚刚看完电影《第39级台阶》。离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
请你利用计算机的优势，帮助小明寻找答案。
数组写法：
public class Main {
public static void main(String[] args) {
int step[][] = new int[40][2]; //二维数组的第一维代表台阶，第二维代表左右脚
//0：左脚 1：右脚
step[1][0] = 1; //左脚上第1阶台阶的方法有1种
step[1][1] = 0; //右脚上第1阶台阶的方法有0种
step[2][0] = 1; //左脚上第2阶台阶的方法有1种
step[2][1] = 1; //右脚上第2阶台阶的方法有1种
for(int i=3; i<=39; ++i){
step[i][0] = step[i-1][1]+step[i-2][1];
step[i][1] = step[i-1][0]+step[i-2][0];
}
System.out.println(step[39][1]);
}
}递归写法：
public class Main {
public static void main(String[] args) {
System.out.println(right(39));
}
static int left(int n){
if(n==1) return 1;
if(n==2) return 1;
return right(n-1)+right(n-2);
}
static int right(int n){
if(n==1) return 0;
if(n==2) return 1;
return left(n-1)+left(n-2);
}
}第五题：找钱问题
公园票价为5角。假设每位游客只持有两种币值的货币：5角、1元。
再假设持有5角的有m人，持有1元的有n人。
由于特殊情况，开始的时候，售票员没有零钱可找。
我们想知道这m+n名游客以什么样的顺序购票则可以顺利完成购票过程。
显然，m < n的时候，无论如何都不能完成；
m>=n的时候，有些情况也不行。比如，第一个购票的乘客就持有1元。
请计算出这m+n名游客所有可能顺利完成购票的不同情况的组合数目。
注意：只关心5角和1元交替出现的次序的不同排列，持有同样币值的两名游客交换位置并不算做一种新的情况来计数。
考虑最后一个人：
import java.util.Scanner;
/*从最后一个人开始考虑*/
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int m=cin.nextInt();
int n=cin.nextInt();
System.out.println(f(m,n));
}
static int f(int m,int n){
if(m<n) return 0; //当5角的个数少于1元的个数时，无论如何也是无法成功的，所以返回0
if(n==0) return 1; //当一元的个数为0时，就只有一种排队顺序，即：555555......
if(m==0) return 0; //当5角的个数为0时，也无法排出题目要求的顺序
return f(m-1,n)+f(m,n-1); //当前最后一个为5角 or 1元
}
}下一篇： RabbitMQ