遞歸
棧結(jié)構 層層調(diào)用 層層返回
設計遞歸有三個步驟

1. 找重復
2. 找變化
3. 找邊界

public static void main(String[] args) {
        f(10);
    }
    //注意死循環(huán)
    static void f(int i) {
        if (i ==0) {
            return;
        }
        //調(diào)用自身
        f(i-1);
    }

n的階乘

public static void main(String[] args) {
        System.out.println(f(4));
    }
/*  
 *  f(n):求n的階乘 -- > f(n-1)求n-1的階乘
 *  1.  找重復 n*(n-1)的階乘,求n-1的階乘是原問題的重復（規(guī)模更?。?-子問題
    2.  找變化  變化的量應該作為參數(shù)
    3.  找邊界 出口
    */
    static int f(int n) {
        if(n==1) {
            return 1;
        }
        return n * f(n-1);
    }

打印 i 到 j （委托思想 偷懶思想 我只做一部分（盡可能小的一部分） 剩下部分 我交給其他人做 ）

    public static void main(String[] args) {
        f(10,20);
    }
    static void f(int i,int j) {
        if(i>j){
            return;
        }
        System.out.println(i);
        f(i+1,j);
    }

對arr的所有元素求和 （Array 數(shù)組）

public static void main(String[] args) {
        int res = f(new int[] {1,2,3,4,5},0);
        System.out.println(res);
    }
    static int f(int[] arr,int beign) {//這個變化當中去找參數(shù) 加參數(shù)是設計遞歸的一個難點 很多人切完蛋糕的一小塊 不知道該怎么寫 這時候你要想想是不是缺參數(shù)
                                     //begin是那個變化量 不停地往前推進 arr是一個常量
        if(beign == arr.length-1) { //當begin 等于數(shù)組最后一個的下標 就不用再求和 就直接返回那個值即可
            return arr[beign];
        }
        return arr[beign] + f(arr,beign+1);
    }
>>> 15

翻轉(zhuǎn)字符串

public static void main(String[] args) {
        System.out.println(f("abcd",3)); // a b c d 反轉(zhuǎn) 從后面切一刀 d + （a b c）以后同理  當然也可以從前面切一刀 但是好像沒有變化的值了 
    }
    
    static String f(String src,int end) {
        if(end == 0) {
            return ""+src.charAt(end);//""+是為了轉(zhuǎn)為String類型
        }
        return src.charAt(end)+f(src,end-1);
    }
>>>dcba

重復中找變化 ，變化中找重復

斐波那契數(shù)列
首先斐波那契數(shù)列 是這樣的一個數(shù)列 1 1 2 3 5 8 13
每一項都是前兩項的和 求第N項斐波那契數(shù) 這個N是第n項 本身無法參與運算 不像我們階乘那個
這個也符合我們拆解成更小規(guī)模的子任務 ，但是這個地方要拆解成兩個子任務
一個小弟去求n-1 一個小弟去求n-2 我只負責把他們合起來
這是遞歸的一種變體

遞歸包括：

分解為：直接量+小規(guī)模子問題

也可以分解為：多個（兩個及兩個以上）小規(guī)模子問題

這個問題 需要拆 和 湊
劃一刀 解決一部分 再劃一刀 再解決一部分 去拆去湊

public static void main(String[] args) {
        System.out.println(f(5)); 
    }
    static int f(int n) {
        if(n==1||n ==2) {
            return 1;
        }
        return f(n-1)+f(n-2);
    }
>>>5

畫出遞歸示意圖 你會發(fā)現(xiàn)很有意思的事情
之前 那些 比如求10的階乘 他們是單路徑 沒有分支 一條路徑走下來
但是我們做斐波那契數(shù)列時 開叉了
這個叫做遞歸解答樹

這個是 每個點都要開叉
你會發(fā)現(xiàn) 有大量重復的求解 以后我們?nèi)?yōu)化
調(diào)用過程 比如 求解f(6)時 f5 和f4是同時進行的嗎 顯然不是
是先左子樹 再右子樹 返回來 再求兄弟（也是先求兄弟的左子樹 再求兄弟的右子樹）

最大公約數(shù)
輾轉(zhuǎn)相除法
m % n等于0時 n是最大公約數(shù)，m%n 余數(shù)是k 則接下來 n%k 再進行判斷
如果要寫成公式則
f(m,n) = f(n,m%n)

public static void main(String[] args) {
        System.out.println(f(33,10));
    }
    static int f(int m,int n) {
        if(n==0) {
            return m;
        }
        return f(n,m%n);
    }

總而言之 你能找到問題的演變 推進的方式 本質(zhì)上來講都可以寫成遞推公式
只要在遞推范圍中再越縮越小 也就是在問題的規(guī)模在 越減越小 就是成功的遞推設計

插入排序改遞歸

對數(shù)組的0~倒數(shù)第一個 排序
等價于：
對數(shù)組的0~倒數(shù)第二個元素，這部分排序
然后把最后一個元素插入到這個有序的部分中

public static void main(String[] args) {
        int[] arr = new int[]{3,2,4,1};
        f(arr,3);
        for(int i =0;i<=arr.length-1;i++) {
            System.out.println(arr[i]+" ");
        }
        
    }
    
    static void f(int[]arr,int k) {
        if(k ==0) {
            return;
        }
        //對前k-1部分進行排序
        f(arr,k-1);
        //對位置k的元素插入到前面的部分
        int x = arr[k];//假設是3241 保存數(shù)組序列號為k（這里是3）的值是1
        int index = k-1;//保存下一個要比較的序列號k-1（這里是2）
        while(index>-1&&x<arr[index]) {//注意這個坑index>-1 因為1要和序列號為0的進行比較 比較后滿足條件 arr[1]=arr[0] 后減1 index就變?yōu)?1了 
            arr[index+1] = arr[index];
            index--;
        }
        arr[index+1] = x;//注意這個坑 index+1 因為最后符合條件前多減了一次 ，index =-1此時是要把1插入到數(shù)組中 所以 index+1 為0
    }
>>>1 2 3 4 

總結(jié)

• 找重復

  • 方法1找到一種劃分方法
  • 方法2找到遞推公式或者等價轉(zhuǎn)換
    都是父問題轉(zhuǎn)化為求解子問題

• 找變化的量
  變化的量通常要作為參數(shù)
  如果找變化的量困難 要不是參數(shù)不夠 要不就沒找到隱含的參數(shù)

• 找出口‘

所有的循環(huán)語句一定能改成遞歸 有的簡單 有的難

漢諾塔
1-N從A移到B，C作為輔助 B為最終的目標柱子
等價于：
1、1~N-1從A移動到C B作為輔助
2、把N從A移動到B
3、1-N-1從C移動到B，A作為輔助
其中 每部 都直接是結(jié)果，不表示過程
難點就是N從A到B后 就可以把B作為空柱子 不用再管N 問題也就等價
最難想的就是轉(zhuǎn)換柱子的角色 柱子的角色在變 把柱子作為參數(shù)就可以了
除了規(guī)模在變化以外 從哪到哪 以誰為輔助（柱子角色） 都在變化

圖不全

    public static void main(String[] args) {
        f(3,"A","B","C");
    }
    /**
     * 將N個盤子從source移動到target的路徑打印
     * @param N 初始的N個從小到大的盤中，N是最大的編號
     * @param from  原始柱子
     * @param to    目標柱子
     * @param help  輔助柱子
     */
    static void f(int N,String from,String to,String help) {
        if(N==1){
            System.out.println("move "+N+" from "+from+" to "+to);
            return;
        }
        f(N-1,from,help,to);//先把前N-1個盤子挪到輔助空間去
        System.out.println("move "+N+" from "+from+" to "+to);//N可以順利到達目標柱子
        f(N-1,help,to,from);//讓N-1個盤子回到目的空間去
      //注意調(diào)用方法，除了數(shù)值越變越小，這三個柱子的角色 也在互相變化  誰為參考點 誰為目標 它在變化
    }
>>>move 1 from A to B
>>>move 2 from A to C
>>>move 1 from B to C
>>>move 3 from A to B
>>>move 1 from C to A
>>>move 2 from C to B
>>>move 1 from A to B