遞歸分類

• 分解為直接量+小規(guī)模子問題
  • 不伴隨著參數(shù)角色的變化
  • 伴隨著參數(shù)角色的變化（調(diào)用遞歸時除了縮小參數(shù)，還要調(diào)換參數(shù)的位子）
• 分解為多個小規(guī)模子問題
  • 子問題不等價 f(M)+f(N)
  • 子問題等價 f(N/k)+...+f(N/k)
• 不分解，但是規(guī)模不斷縮小

例1：求階乘

【#分解為直接量+小規(guī)模子問題，不伴隨著參數(shù)角色的變化】
【思考】這道題典型的"切蛋糕",在前面切一刀，并且只有一個參數(shù)。

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：數(shù)組求和

【#分解為直接量+小規(guī)模子問題，不伴隨著參數(shù)角色的變化】
【思考】這道題典型的"切蛋糕",在前面切一刀，但是有兩個參數(shù)，兩個參數(shù)沒有角色交換，只是其中一個參數(shù)不斷縮小規(guī)模。

import java.util.*;
public class Main{
    public static void main(String args[]){
  //先創(chuàng)建一個儲存0~n-1的數(shù)組
        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;
       }
//調(diào)用函數(shù)
        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：字符串翻轉(zhuǎn)

【#分解為直接量+小規(guī)模子問題，不伴隨著參數(shù)角色的變化】
【思考】這道題典型的"切蛋糕",但是在后面切一刀，有兩個參數(shù)，兩個參數(shù)沒有角色交換，其中一個參數(shù)不斷縮小規(guī)模。

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：漢諾塔

在印度，有這么一個古老的傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。
假設(shè)三根針分別是A,B,C，用戶輸入金片個數(shù)N，起初這N個金片全部在A針上，那么漢諾塔金片全部移動到B針上時需要移動的最少步數(shù)是多少？
【#分解為直接量+小規(guī)模子問題，伴隨著參數(shù)角色的變化（調(diào)用遞歸時除了縮小參數(shù)，還要調(diào)換參數(shù)的位子）】
【思考】
1、為什么選擇先把最大（放在最底下）的金片放在目標(biāo)針，再把剩下的挪到目標(biāo)針？因為大的放好以后就可以不用動了，而且這根針還可以放其它金片，因為其它金片都比放好的金片小。
2、最開始所有金片都在A上，要把金片移動到B上，C作為輔助針。挪動最底下的金片之前要先把上面的所有金片挪到輔助針上，再挪動最底下的金片到目標(biāo)針，然后把當(dāng)前輔助針上的金片挪到目標(biāo)針上。假如有N個金片需要挪動，那么剛剛已經(jīng)完成了N個金片的挪動，但忽略了前N-1個金片的挪動細(xì)節(jié)。當(dāng)我們要移動前N-1個金片時，可以把它想象成是挪動N個金片，但是參數(shù)對應(yīng)的角色變了，對于第1~N-1個金片，當(dāng)它們從A到C時，它們的目標(biāo)針是C，A是起始針，B是輔助針；第N個金片放好以后，要把其它金片從C挪到B，這個時候A成為了輔助針，而B是目標(biāo)針，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);  //參數(shù)角色變化
        System.out.println("把"+N+"從"+from+"移到"+to);
       hanNuoTa(N-1,help,to,from);  //參數(shù)角色變化
        }
    }    
}

例5:斐波拉契數(shù)列求和

【#分解為多個小規(guī)模子問題,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：輾轉(zhuǎn)相除法求最大公約數(shù)

【 #不分解，但是規(guī)模不斷縮小】
【知識點】輾轉(zhuǎn)相除法求最大公約數(shù)的原理：舉個例子，求511和292的最大公約數(shù)。511/292=1......219; 292/219=1......73; 219/73=3; 最大公約數(shù)為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);
    }
}