Java?精煉解讀遞歸的概念與使用

更新時(shí)間：2022年03月15日 14:25:23 作者：K穩(wěn)重

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

一、遞歸的概念

1.什么是遞歸？

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

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

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

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

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

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

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

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

2.遞歸講解

首先看下面代碼：

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

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

我們再來看一下這個(gè)代碼的運(yùn)行結(jié)果，

畫圖講解：

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

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

老鐵們要記?。阂坏┠銓懙倪f歸有問題，如果是邊界沒找對一定會報(bào)一個(gè)

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

如果想要讓上述代碼正確，我們需要給它加入一個(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);
 
    }
}

下面會通過簡單的例題讓大家更加深入的了解遞歸

二、遞歸的使用

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

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

代碼畫圖講解：

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

例題：求n的和

畫圖分析：

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 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));
 
    }
}
 
第二種寫法：
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ù)字

畫圖分析：

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

例題：寫一個(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ù)是幾

畫圖分析：

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