一說(shuō)起遞歸，我想每個(gè)人都不陌生。舉個(gè)從小就聽(tīng)過(guò)的例子：從前有座山，山里有座廟，廟里有個(gè)和尚，和尚在講故事，從前有座山，山里有座廟，廟里有個(gè)和尚，和尚在講故事，從前有座山，要理解遞歸，就得先了解什么是遞歸，實(shí)際上這句話就是一個(gè)遞歸

一、遞歸的概念

1.什么是遞歸？

遞歸就是：方法自己調(diào)用方法的過(guò)程。

使用遞歸有兩個(gè)前提條件：

1.有一個(gè)趨近與終止的條件。

2.自己調(diào)用自己。

如何實(shí)現(xiàn)遞歸？

最重要的方式是：實(shí)現(xiàn)遞歸，需要去推導(dǎo)出一個(gè)遞推公式。

思考遞歸的方式：橫向思考，根據(jù)遞推公式來(lái)思考。

代碼的執(zhí)行：是縱向執(zhí)行。

2.遞歸講解

首先看下面代碼：

public class TestDemo {
    public static void func(){
        
        func();   //自己調(diào)用自己本身
    }
 
 
    public static void main(String[] args) {
        func();
 
    }
}

上圖代碼就是一個(gè)簡(jiǎn)單的遞歸。

我們?cè)賮?lái)看一下這個(gè)代碼的運(yùn)行結(jié)果，

畫(huà)圖講解：

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS-WqvuKAjQ==,size_20,color_FFFFFF,t_70,g_se,x_16

對(duì)于上圖這個(gè)遞歸來(lái)說(shuō)，根本沒(méi)有一個(gè)趨于終止的條件，所以這個(gè)函數(shù)會(huì)無(wú)休止的遞歸下去。每次遞歸都要在棧上開(kāi)辟內(nèi)存，一直在棧上開(kāi)辟內(nèi)存，總有一次會(huì)棧超出。

老鐵們要記住：一旦你寫(xiě)的遞歸有問(wèn)題，如果是邊界沒(méi)找對(duì)一定會(huì)報(bào)一個(gè)

，如果報(bào)了這個(gè)錯(cuò)誤那么一定是你的終止條件有錯(cuò)誤，或者是沒(méi)寫(xiě)終止條件導(dǎo)致了你在遞歸的過(guò)程當(dāng)中深度過(guò)大，最終棧溢出。

如果想要讓上述代碼正確，我們需要給它加入一個(gè)終止條件。

正確代碼如下：

public class TestDemo {
    public static void func(int n){
        if(n == 1) return;
        func(n -1);
    }
 
 
    public static void main(String[] args) {
        func(3);
 
    }
}

下面會(huì)通過(guò)簡(jiǎn)單的例題讓大家更加深入的了解遞歸

二、遞歸的使用

例題：遞歸方式求n的階乘畫(huà)圖分析：

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS-WqvuKAjQ==,size_20,color_FFFFFF,t_70,g_se,x_16

實(shí)現(xiàn)代碼：

public class TestDemo {
    public static int fac(int n){
        if(n == 1) {
            return 1;
        }
        int tmp = n * fac(n - 1);
        return tmp;
    }
    public static void main(String[] args) {
        System.out.println(fac(5));
 
    }
}

代碼畫(huà)圖講解：

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS-WqvuKAjQ==,size_20,color_FFFFFF,t_70,g_se,x_16

例題：求n的和

畫(huà)圖分析：

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS-WqvuKAjQ==,size_20,color_FFFFFF,t_70,g_se,x_16

實(shí)現(xiàn)代碼：

第一種寫(xiě)法：
public class TestDemo {
    public static int sumAdd(int n){
        if(n == 1) {
            return 1;
        }
        int tmp = n + sumAdd(n - 1);
        return tmp;
    }
    public static void main(String[] args) {
        System.out.println(sumAdd(3));
 
    }
}
 
第二種寫(xiě)法：
public class TestDemo {
    public static int sumAdd(int n){
        if(n == 1) {
            return 1;
        }
       
        return n + sumAdd(n -1);
    }
    public static void main(String[] args) {
        System.out.println(sumAdd(3));
 
    }
}

例題：遞歸實(shí)現(xiàn)按照順序打印每一位的數(shù)字

畫(huà)圖分析：

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS-WqvuKAjQ==,size_20,color_FFFFFF,t_70,g_se,x_16

實(shí)現(xiàn)代碼：

public class TestDemo {
 
    public static void print(int n){
        if(n < 10){
            System.out.print(n+" ");
        }else{
            print(n/10);
            System.out.print(n%10+" ");
        }
    }
    public static void main(String[] args) {
        print(1234);
 
 
    }
}

例題：寫(xiě)一個(gè)遞歸方法，輸入一個(gè)非負(fù)整數(shù)，返回組成它的數(shù)字之和。例如：輸入1729，則應(yīng)該返回1+7+2+9

實(shí)現(xiàn)代碼：

public class TestDemo {
 
 
    public static int sumEveryone(int n){
        if(n < 10){
           return n;
        }else{
            return n%10 + sumEveryone(n/10);
        }
    }
 
    public static void main(String[] args) {
        System.out.println(sumEveryone(7910));
 
    }
 
}

例題：求第n個(gè)斐波那契數(shù)是幾

畫(huà)圖分析：

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS-WqvuKAjQ==,size_20,color_FFFFFF,t_70,g_se,x_16

實(shí)現(xiàn)代碼:

第一種方法：遞歸
public class TestDemo {
    public static int fib(int n){
        if(n == 1 || n == 2){
            return 1;
        }else{
            return fib(n-2)+fib(n-1);
        }
    }
    public static void main(String[] args) {
        System.out.println(fib(5));
 
    }
 
 
 
第二種方法：叫做循環(huán)(迭代）實(shí)現(xiàn)
    public static int fib2(int n){
        if(n == 1 || n==2){
            return 1;
        }
            int f1 = 1;
            int f2 = 1;
            int f3 = 0;
            for (int i = 3; i < n; i++) {
                f3 = f1+f2;
                f1 = f2;
                f2 = f3;
            }
            return f3;
 
    }
    public static void main(String[] args) {
        System.out.println(fib2(45));
 
    }

總結(jié)：

本文簡(jiǎn)單介紹了什么是遞歸、遞歸講解、遞歸如何使用。通過(guò)簡(jiǎn)單例題的方式加深對(duì)遞歸的印象。上述就是今天的內(nèi)容，文章哪里出現(xiàn)了問(wèn)題我都會(huì)積極改正，也希望大家能更快的掌握自己想要的知識(shí)，讓我們一起加油！?。。?！

到此這篇關(guān)于Java 精煉解讀遞歸的概念與使用的文章就介紹到這了,更多相關(guān)Java 遞歸內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: