遞歸入門

遞歸

什麼是遞歸？ 直接或間接的調用自身的算法稱為遞歸算法，打趣的來說 就是 “自己玩自己”。既然遞歸是一個反複調用自身的過程，這就說明它每一級的功能都是一樣的，是以隻需關注一級遞歸的解決過程即可。

從 bokeyuan部落客 三年一夢的總結中，解遞歸題的三部曲：

1，找整個遞歸的終止條件：遞歸應該在什麼時候結束？

2， 找傳回值：應該給上一級傳回什麼資訊？

3，本級遞歸應該做什麼：在這一級遞歸中，應該完成什麼任務？

疊代

疊代是利用變量的原值推算出變量的一個新值，如果遞歸是自己調用自己的話,疊代就是A不停的調用B。也就是，遞歸是自己玩自己，疊代是自己玩别人。

遞歸經典例題

例1: n的階乘

package com.company;

import java.math.BigInteger;
import java.util.Scanner;
public class N_ {
    public static void main(String[] args) {
        System.out.println("求數字幾的階乘啊？");
        Scanner a = new Scanner(System.in);
        int b = a.nextInt();
        System.out.println(ade(b));

    }   

    public static long ade(long c) {
        if (c <= 0) {
            return 0;
        } else if (c == 1) {
            return 1;
        } else return c * ade(c - 1);
    }
}

           

對代碼加入了scanner，可以擷取任意數的階乘，需要注意的是 int可表示範圍， 在java中，int 最多到12的階乘，long最多到20，BigInteger随意精度，運算符應用受限（暫時還不會用）。

例2:斐波納切數列

package com.company;
import java.util.Scanner;
public class factorial {
    public static void main(String[] args) {
        System.out.println("請輸入n:");
        Scanner a = new Scanner(System.in);
        String b = a.next();
        int c = Integer.parseInt(b);
        System.out.println(func(c));

    }

    public static int func(int n) {
        if (n < 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return n * func(n - 1);
        }
    }
}

           

例3: 漢諾塔問題

（1） 最後盤子都放在B上

package com.company;
import java.util.Scanner;


public class Hnaoi{
    static int times;
    public static void main(String[] args) {
        char A = 'A';
        char B = 'B';
        char C = 'C';

        Scanner q = new Scanner(System.in);
        System.out.println("請輸入盤子數：");
        int n = q.nextInt();
        hno(n,A,B,C);


    }
    public static void move(int Disk, char M,char N){
        System.out.println("第"+(++times)+"次移動，盤子" +Disk+"  " +M +"到"+N);
    }

    public static void hno(int n,char A,char B,char C){
        if( n == 1){
            move(1,A,B);
        }else {
            hno(n-1,A,C,B);
            move(n,A,B);
            hno(n-1,C,B,A);
        }
    }
}
           

（2） 盤子全部放C上

public class Hnaoi {
    static int times;
    public static void main(String[] args) {
        char A = 'A';
        char B = 'C';
        char C = 'B';
        System.out.println("漢諾塔遊戲開始！！");
        System.out.println("請輸入盤子數：");
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        hna(n,A,B,C);

    }

    public static void move(int disk,char M,char N){
        System.out.println("第" +(++times)+ "次移動. 盤子" + disk +"  "+ M+ "--->" +N);
    }
    public static void hna(int n,char A,char B,char C){
        if (n == 1){
            move(n,A,C);
        }else {
            //移動上一關的步驟到B
            hna(n-1,A,C,B);
            //吧最大盤子移動到C
            move(n,A,C);
            //再把c上上一關移動的盤子放到b上就可以了
            hna(n-1,B,A,C);  //B --C


        }
    }
    }
           

例4: 搜尋二叉樹深度

public class BinaryTreeDepth {
ic static int getTreeDepth(Tree t) {
        // 樹為空
        if (t == null) // 遞歸終止條件
            return 0;
 
        int left = getTreeDepth(t.left); // 遞歸求左子樹深度，縮小問題的規模
        int right = getTreeDepth(t.left); // 遞歸求右子樹深度，縮小問題的規模
 
        return left > right ? left + 1 : right + 1;
    }
}
           

上述例題均為遞歸算法入門題，後續要在Leetcode多做幾道遞歸題，加深了解。

leetcode.344.反轉字元串（困難等級：簡單）。

題目：編寫一個函數，其作用是将輸入的字元串反轉過來。輸入字元串以字元數組 char[] 的形式給出。不要給另外的數組配置設定額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。你可以假設數組中的所有字元都是 ASCII 碼表中的可列印字元。

public void res(char[] s) {
        trs(s, 0, s.length-1);
        }
        public void trs(char[] s, int start, int end) {
            if(start > end)
                return;

            trs(s, start+1, end-1);
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
        }