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

遞歸的必要條件：

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

2. 遞歸出口。

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

遞歸過(guò)程分析：

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

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

函數(shù)開(kāi)始, n = 5
函數(shù)開(kāi)始, n = 4
函數(shù)開(kāi)始, n = 3
函數(shù)開(kāi)始, n = 2
函數(shù)開(kāi)始, 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

運(yùn)行結(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è)計(jì)，本題我們想得到1+……10的和，來(lái)看我們的遞歸體如何設(shè)計(jì)的！

運(yùn)行結(jié)果：

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

問(wèn)題分析：比如我們想打印1234的每一位，那么打印出來(lái)應(yīng)該就是1 2 3 4那么首先就是如何判斷我們輸入的數(shù)字是幾位數(shù)，看下面的功能代碼部分，設(shè)計(jì)非常的巧妙，通過(guò)是否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);
    }
}

運(yùn)行結(jié)果：

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

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

函數(shù)實(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));
    }
}

運(yùn)行結(jié)果：

求解漢諾塔問(wèn)題

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

代碼實(shí)現(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');
    }
}

代碼解讀：通過(guò)定義我們可以了解到每次只能移動(dòng)一個(gè)盤(pán)子，并且小盤(pán)子要放在大盤(pán)子上面，那么這里我們有A B C，三個(gè)圓柱，我們可以將其依次理解為：初始位置   跳板位置  目標(biāo)位置，我們看函數(shù)部分，如果只有一個(gè)盤(pán)子我們直接從A->C 只需移動(dòng)一步便可，那么>1的情況，這里我們假設(shè)要移動(dòng)三個(gè)盤(pán)子，通過(guò)畫(huà)圖我們可以發(fā)現(xiàn)首先要將2個(gè)盤(pán)子移動(dòng)到B圓柱再借助A移動(dòng)到C盤(pán)，那么這里的第一次調(diào)用 han(n-1,pos1,pos3,pos2);我們便可以理解，下次遞歸將（n-1）作為盤(pán)子個(gè)數(shù)，pos1就是我們的起始位置，pos3就是我們的跳板位置，pos2就是我們的目標(biāo)位置，因?yàn)槭紫任覀儗?n-1）個(gè)盤(pán)子放在了B（pos2）上，調(diào)用結(jié)束后，執(zhí)行我們的move函數(shù)，輸出我們這次的移動(dòng)軌跡，下次調(diào)用就是han(n-1,pos2,pos1,pos3);同理，這個(gè)時(shí)候pos2就是我們的起始位置,pos1變成我們的跳板位置，最后pos3是我們的目標(biāo)位置。

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

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

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

那么，談及遞歸的運(yùn)算不得不提斐波那契數(shù)列這樣的經(jīng)典問(wèn)題，下面就給大家展示一下Java語(yǔ)言的代碼實(shí)現(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)在遞歸的過(guò)程中，如果我們要求斐波那契數(shù)列的前40項(xiàng) 50項(xiàng)的和，以40項(xiàng)為例我們首先需要求 39項(xiàng) 38項(xiàng)的結(jié)果，而要得到39項(xiàng)的和我們要求出38的項(xiàng)的結(jié)果和37項(xiàng)的結(jié)果，進(jìn)而上個(gè)38項(xiàng)的結(jié)果我們需要在求一次，這樣發(fā)現(xiàn)我們有很多次的重復(fù)計(jì)算，造成了很不必要的浪費(fèi)，那么我們可以通過(guò)for循環(huán)的方式來(lái)減少代碼冗余度。

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

運(yùn)行結(jié)果：

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

最新評(píng)論