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

上圖代碼就是一個簡單的遞歸。

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

畫圖講解：

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

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

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

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

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

正確代碼如下：

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

例題：寫一個遞歸方法，輸入一個非負(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個斐波那契數(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));
 
    }