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

Posted on by

遞歸定義：一個方法在執行過程中調用自身, 就稱為 "遞歸"。

遞歸的必要條件：

1. 將原問題劃分成其子問題，註意：子問題必須要與原問題的解法相同。

2. 遞歸出口。

一、實例演示：遞歸求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;
}

運行結果：

到此這篇關於基於Java語言的遞歸運算例題詳解的文章就介紹到這瞭,更多相關Java遞歸運算內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：