Java遞迴：概念與用法

一、遞迴的概念

1.什麼是遞迴？

遞迴就是：方法自己呼叫方法的過程。

使用遞迴有兩個前提條件：

1.有一個趨近與終止的條件。

2.自己呼叫自己 。

如何實作遞迴？

最重要的方式是：實作遞歸，需要去推導出一個遞推公式。

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

程式碼的執行：是縱向執行。

2.遞迴講解

先看下面程式碼：

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

上圖程式碼就是一個簡單的遞迴。

我們再來看這個程式碼的運行結果，

畫圖講解：

# 對於上圖這個遞歸來說，根本沒有一個趨於終止的條件，所以這個函數會無止盡的遞歸下去。每次遞迴都要在棧上開闢內存，一直在棧上開闢內存，總有一次會棧超出。

老鐵們要記住：一旦你寫的遞歸有問題，如果是邊界沒找對一定會報一個

##，如果報了這個錯誤那麼一定是你的終止條件有錯誤，或是沒寫終止條件導致了你在遞歸的過程當中深度過大，最終棧溢出。

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

正確程式碼如下：

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的階乘  畫圖分析：

實作程式碼：

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

程式碼畫圖解說：

範例：求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));
 
    }
}

範例：遞迴實作依照順序列印每一位的數字 

畫圖分析：

 實作程式碼：

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

範例：寫一個遞迴方法，輸入一個非負整數，返回組成它的數字總和。例如：輸入1729，則應該回傳1 7 2 9

實作碼：

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個斐波那契數是幾 

#畫圖分析：

實作程式碼:

第一种方法：递归
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));
 
    }
 
 
 
第二种方法：叫做循环(迭代）实现
    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));
 
    }

以上是Java遞迴：概念與用法的詳細內容。更多資訊請關注PHP中文網其他相關文章！