递归分类
- 分解为直接量+小规模子问题
- 不伴随着参数角色的变化
- 伴随着参数角色的变化（调用递归时除了缩小参数，还要调换参数的位子）
- 分解为多个小规模子问题
- 子问题不等价 f(M)+f(N)
- 子问题等价 f(N/k)+...+f(N/k)
- 不分解，但是规模不断缩小
例1：求阶乘
【#分解为直接量+小规模子问题，不伴随着参数角色的变化】
【思考】这道题典型的"切蛋糕",在前面切一刀，并且只有一个参数。
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int n=in.nextInt();
System.out.println(jieCheng(n));
}
static int jieCheng(int n){
if(n==1)
return 1;
return n*jieCheng(n-1);
}
}
例2：数组求和
【#分解为直接量+小规模子问题，不伴随着参数角色的变化】
【思考】这道题典型的"切蛋糕",在前面切一刀，但是有两个参数，两个参数没有角色交换，只是其中一个参数不断缩小规模。
import java.util.*;
public class Main{
public static void main(String args[]){
//先创建一个储存0~n-1的数组
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=i;
}
//调用函数
System.out.println(sum_arr(0,arr));
}
static int sum_arr(int i,int[] arr){
if(i==arr.length-1)
return arr[i];
return arr[i]+sum_arr(i+1,arr);
}
}
例3：字符串翻转
【#分解为直接量+小规模子问题，不伴随着参数角色的变化】
【思考】这道题典型的"切蛋糕",但是在后面切一刀，有两个参数，两个参数没有角色交换，其中一个参数不断缩小规模。
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
String s=in.next();
System.out.println(reverse(s,s.length()-1));
}
static String reverse(String s,int end){
if(end==0){
return ""+s.charAt(end);
}
return s.charAt(end)+reverse(s,end-1);
}
}
例4：汉诺塔
在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
假设三根针分别是A,B,C，用户输入金片个数N，起初这N个金片全部在A针上，那么汉诺塔金片全部移动到B针上时需要移动的最少步数是多少？
【#分解为直接量+小规模子问题，伴随着参数角色的变化（调用递归时除了缩小参数，还要调换参数的位子）】
【思考】
1、为什么选择先把最大（放在最底下）的金片放在目标针，再把剩下的挪到目标针？因为大的放好以后就可以不用动了，而且这根针还可以放其它金片，因为其它金片都比放好的金片小。
2、最开始所有金片都在A上，要把金片移动到B上，C作为辅助针。挪动最底下的金片之前要先把上面的所有金片挪到辅助针上，再挪动最底下的金片到目标针，然后把当前辅助针上的金片挪到目标针上。假如有N个金片需要挪动，那么刚刚已经完成了N个金片的挪动，但忽略了前N-1个金片的挪动细节。当我们要移动前N-1个金片时，可以把它想象成是挪动N个金片，但是参数对应的角色变了，对于第1~N-1个金片，当它们从A到C时，它们的目标针是C，A是起始针，B是辅助针；第N个金片放好以后，要把其它金片从C挪到B，这个时候A成为了辅助针，而B是目标针，C是起始针。
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int N=in.nextInt();
hanNuoTa(N,"A","B","C");
}
static void hanNuoTa(int N,String from,String to,String help){
if(N==1){
System.out.println("把"+N+"从"+from+"移到"+to);
}
else{
hanNuoTa(N-1,from,help,to); //参数角色变化
System.out.println("把"+N+"从"+from+"移到"+to);
hanNuoTa(N-1,help,to,from); //参数角色变化
}
}
}
例5:斐波拉契数列求和
【#分解为多个小规模子问题,f(M)+f(N)】
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
System.out.println(fib(in.nextInt()));
}
static int fib(int n){
if(n==1||n==2)
return 1;
return fib(n-1)+fib(n-2);
}
}
例6：辗转相除法求最大公约数
【 #不分解，但是规模不断缩小】
【知识点】辗转相除法求最大公约数的原理：举个例子，求511和292的最大公约数。511/292=1......219; 292/219=1......73; 219/73=3; 最大公约数为73。
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
System.out.println(gcd(in.nextInt(),in.nextInt()));
}
static int gcd(int m,int n){
if(m%n==0)
return n;
return gcd(n,m%n);
}
}
