遞歸定義：一個方法在執(zhí)行過程中調(diào)用自身, 就稱為 "遞歸"。

遞歸的必要條件：

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

2. 遞歸出口。

一、實例演示：遞歸求N的階乘

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

遞歸過程分析：

本題假設(shè)我們想求解5的階乘，我們可以看到我們從main函數(shù)里面輸入一個數(shù)N，這里我們輸入5，隨即在我們的功能函數(shù)factorial接收到參數(shù)5，接著因為if里面的條件是x<2，不滿足，所以執(zhí)行我們的else里面的語句，我們發(fā)現(xiàn)是return x * factorial(x-1);我們輸入的是5，所以即 return 5   *factorial(4);同理我們調(diào)用了本身這個factorial函數(shù)，傳進(jìn)去的參數(shù)是4，接著繼續(xù)……，直到我們的參數(shù)變成1<2,那么這時遞歸的  “遞” ，結(jié)束，開始我們的 “歸”。

執(zhí)行結(jié)果

函數(shù)開始, n = 5
函數(shù)開始, n = 4
函數(shù)開始, n = 3
函數(shù)開始, n = 2
函數(shù)開始, n = 1
函數(shù)結(jié)束, n = 1 ret = 1
函數(shù)結(jié)束, n = 2 ret = 2
函數(shù)結(jié)束, n = 3 ret = 6
函數(shù)結(jié)束, n = 4 ret = 24
函數(shù)結(jié)束, n = 5 ret = 120
ret = 120

運行結(jié)果：

二、 遞歸調(diào)用練習(xí)

遞歸求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));
    }
}

遞歸的核心思想就是我們的遞歸體應(yīng)該如何設(shè)計，本題我們想得到1+……10的和，來看我們的遞歸體如何設(shè)計的！

運行結(jié)果：

順序打印一個數(shù)字的每一位

問題分析：比如我們想打印1234的每一位，那么打印出來應(yīng)該就是1 2 3 4那么首先就是如何判斷我們輸入的數(shù)字是幾位數(shù)，看下面的功能代碼部分，設(shè)計非常的巧妙，通過是否n>9，是->我們遞歸調(diào)用本身傳參數(shù) “n/10”,打印的結(jié)果就是  n%10  這樣肯定得到的就是我們的每一位數(shù)字！

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);
    }
}

運行結(jié)果：

返回一個數(shù)組成本身的數(shù)字之和

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

函數(shù)實現(xiàn)：

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));
    }
}

運行結(jié)果：

求解漢諾塔問題

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

代碼實現(xiàn)：

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，三個圓柱，我們可以將其依次理解為：初始位置   跳板位置  目標(biāo)位置，我們看函數(shù)部分，如果只有一個盤子我們直接從A->C 只需移動一步便可，那么>1的情況，這里我們假設(shè)要移動三個盤子，通過畫圖我們可以發(fā)現(xiàn)首先要將2個盤子移動到B圓柱再借助A移動到C盤，那么這里的第一次調(diào)用 han(n-1,pos1,pos3,pos2);我們便可以理解，下次遞歸將（n-1）作為盤子個數(shù)，pos1就是我們的起始位置，pos3就是我們的跳板位置，pos2就是我們的目標(biāo)位置，因為首先我們將(n-1）個盤子放在了B（pos2）上，調(diào)用結(jié)束后，執(zhí)行我們的move函數(shù)，輸出我們這次的移動軌跡，下次調(diào)用就是han(n-1,pos2,pos1,pos3);同理，這個時候pos2就是我們的起始位置,pos1變成我們的跳板位置，最后pos3是我們的目標(biāo)位置。

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

求斐波那契數(shù)列第N項

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

那么，談及遞歸的運算不得不提斐波那契數(shù)列這樣的經(jīng)典問題，下面就給大家展示一下Java語言的代碼實現(xiàn)：

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));
    }
}

代碼分析：雖然這種遞歸方法很容易理解方便使用，但是我們發(fā)現(xiàn)在遞歸的過程中，如果我們要求斐波那契數(shù)列的前40項 50項的和，以40項為例我們首先需要求 39項 38項的結(jié)果，而要得到39項的和我們要求出38的項的結(jié)果和37項的結(jié)果，進(jìn)而上個38項的結(jié)果我們需要在求一次，這樣發(fā)現(xiàn)我們有很多次的重復(fù)計算，造成了很不必要的浪費，那么我們可以通過for循環(huán)的方式來減少代碼冗余度。

優(yōu)化代碼：

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;
}

運行結(jié)果：

到此這篇關(guān)于基于Java語言的遞歸運算例題詳解的文章就介紹到這了,更多相關(guān)Java遞歸運算內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論