基於Java語言的遞迴運算例題詳解

2022-08-01 22:03:37

一、範例演示：遞迴求N的階乘

public class fac {
    public static int factorial(int x){
        if(x<2){
            return 1;
        }
        else{
           return x * factorial(x-1);//遞迴呼叫本身
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(factorial(n));
    }
}

遞迴過程分析：

本題假設我們想求解5的階乘，我們可以看到我們從main函數裡面輸入一個數N，這裡我們輸入5，隨即在我們的功能函數factorial接收到引數5，接著因為if裡面的條件是x<2，不滿足，所以執行我們的else裡面的語句，我們發現是return x * factorial(x-1);我們輸入的是5，所以即 return 5 *factorial(4);同理我們呼叫了本身這個factorial函數，傳進去的引數是4，接著繼續……，直到我們的引數變成1<2,那麼這時遞迴的 “遞” ，結束，開始我們的 “歸”。

執行結果

函數開始, n = 5
函數開始, n = 4
函數開始, n = 3
函數開始, n = 2
函數開始, n = 1
函數結束, n = 1 ret = 1
函數結束, n = 2 ret = 2
函數結束, n = 3 ret = 6
函數結束, n = 4 ret = 24
函數結束, n = 5 ret = 120
ret = 120

執行結果：

二、遞迴呼叫練習

遞迴求1+2+3+……10的和

public class result {
    public static int fun(int n){
        if(n==1){
            return 1;
        }
        return n+fun(n-1);
    }
    public static void main(String[] args) {
        Scanner scanner  = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(fun(n));
    }
}

遞迴的核心思想就是我們的遞迴體應該如何設計，本題我們想得到1+……10的和，來看我們的遞迴體如何設計的！

執行結果：

順序列印一個數位的每一位

問題分析：比如我們想列印1234的每一位，那麼列印出來應該就是1 2 3 4那麼首先就是如何判斷我們輸入的數位是幾位數，看下面的功能程式碼部分，設計非常的巧妙，通過是否n>9，是->我們遞迴呼叫本身傳引數 “n/10”,列印的結果就是 n%10 這樣肯定得到的就是我們的每一位數位！

public class print {
    public static void fun(int n){
        if(n>9){
            fun(n/10);
        }
        System.out.print(n%10+" ");
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        fun(n);
    }
}

執行結果：

返回一個陣列成本身的數位之和

比如我們輸入1234，輸出就是1+2+3+4=10。

函數實現：

public class sum {
    public static int sumd(int num) {
        if (num < 10)
            return num;
        return num % 10 + sumd(num / 10);
    }
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(sumd(n));
    }
}

執行結果：

求解漢諾塔問題

定義：漢諾塔（Tower of Hanoi），又稱河內塔，是一個源於印度古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

程式碼實現：

public class Hanio {
    public static void han(int n,char pos1,char pos2,char pos3){
        if(n==1){
            move(pos1,pos3);
            return;
        }
        han(n-1,pos1,pos3,pos2);
        move(pos1,pos3);
        han(n-1,pos2,pos1,pos3);
    }
    public static void move(char pos1,char pos2){
 
        System.out.println(pos1+"->"+pos2);
    }
    public static void main(String[] args) {
 
        han(3,'A','B','C');
    }
}

程式碼解讀：通過定義我們可以瞭解到每次只能移動一個盤子，並且小盤子要放在大盤子上面，那麼這裡我們有A B C，三個圓柱，我們可以將其依次理解為：初始位置跳板位置目標位置，我們看函數部分，如果只有一個盤子我們直接從A->C 只需移動一步便可，那麼>1的情況，這裡我們假設要移動三個盤子，通過畫圖我們可以發現首先要將2個盤子移動到B圓柱再借助A移動到C槽，那麼這裡的第一次呼叫 han(n-1,pos1,pos3,pos2);我們便可以理解，下次遞迴將（n-1）作為盤子個數，pos1就是我們的起始位置，pos3就是我們的跳板位置，pos2就是我們的目標位置，因為首先我們將(n-1）個盤子放在了B（pos2）上，呼叫結束後，執行我們的move函數，輸出我們這次的移動軌跡，下次呼叫就是han(n-1,pos2,pos1,pos3);同理，這個時候pos2就是我們的起始位置,pos1變成我們的跳板位置，最後pos3是我們的目標位置。

執行結果：（我們可以自己畫圖嘗試一下看這個結果是否正確）

求斐波那契數列第N項

斐波那契數列指的是這樣一個數列：1，1，2，3，5，8，13，21，34，55，89...這個數列從第3項開始，每一項都等於前兩項之和。

那麼，談及遞迴的運算不得不提斐波那契數列這樣的經典問題，下面就給大家展示一下Java語言的程式碼實現：

public class Fib {
    public static int Fibo(int n){
        if(n<=2){
            return 1;
        }
        else{
            return Fibo(n-1)+Fibo(n-2);
        }
    }
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(Fibo(n));
    }
}

程式碼分析：雖然這種遞迴方法很容易理解方便使用，但是我們發現在遞迴的過程中，如果我們要求斐波那契數列的前40項 50項的和，以40項為例我們首先需要求 39項 38項的結果，而要得到39項的和我們要求出38的項的結果和37項的結果，進而上個38項的結果我們需要在求一次，這樣發現我們有很多次的重複計算，造成了很不必要的浪費，那麼我們可以通過for迴圈的方式來減少程式碼冗餘度。

優化程式碼：

public static int fib(int n) {
  int last2 = 1;
  int last1 = 1;
  int sum = 0;
  for (int i = 3; i <= n; i++) {
    sum = last1 + last2;
    last2 = last1;
    last1 =sum;
 }
  return sum;
}

執行結果：