Java - 遞迴

---

---

Java - 遞迴

遞迴是一種程式設計技術，其中一個方法根據需要呼叫自身以執行子操作。呼叫自身的那個方法被稱為遞迴函式。遞迴主要用於將大型問題分解成較小的問題，然後遞迴地解決它們。遞迴技術使程式碼更易讀和更具表達力。

示例

考慮以下情況：

// recursive method
public int sum(int n){
   // recursive method call
   return n == 1 ? 1 : n + sum(n-1);
}

在這種情況下，我們使用遞迴來獲取n個自然數的和，它可以表示為n + n-1個數的和。使用遞迴，我們將n-1個自然數的和的結果與n相加以獲得所需的結果。

由於遞迴函式會呼叫自身，因此必須存在一個基準條件，根據該條件，遞迴方法可以停止無限地呼叫自身。如果基準條件不存在或永遠不會為真，則它會在程式中導致堆疊溢位。在上面的示例中，我們的基準條件是n為1。

public int sum(int n){
   // base condition
   if(n == 1){
      return 1;
   }
   // recursive call
   return n + sum(n-1);
}

如果我們用負整數呼叫此函式，則會導致堆疊溢位錯誤。

Java 中的遞迴是如何工作的？

在 Java 中，變數、方法呼叫、引用儲存在堆疊中，而物件則在堆中分配記憶體。每當呼叫一個方法時，它的詳細資訊都會被壓入堆疊，例如傳遞的引數的值、任何區域性變數、計算等等。在遞迴呼叫期間，每當一個方法呼叫自身時，它的條目就會被壓入堆疊，直到基準條件終止流程。當基準條件為真時，並且方法開始返回值時，子呼叫的結果會從堆疊中彈出，依此類推，直到方法的所有條目都從堆疊中彈出。讓我們用一個例子來理解這一點。

示例

package com.tutorialspoint;

public class Tester {
   public static void main(String[] args) {
      Tester tester = new Tester();
      int result = tester.sum(5);
      System.out.println("Sum: " + result);
   }

   public int sum(int n){
      System.out.println("Input: " + n);
      int result;
      // base condition
      if(n == 1){
         result = 1;
         System.out.println("Base condition fulfilled.");
      }else {
         // recursive call
         result = n + sum(n-1);
      }
      System.out.println("Result: " + result);
      return result;
   }
}

輸出

讓我們編譯並執行上述程式，這將產生以下結果：

Input: 5
Input: 4
Input: 3
Input: 2
Input: 1
Base condition fulfilled.
Result: 1
Result: 3
Result: 6
Result: 10
Result: 15
Sum: 15

在這個程式中，我們可以很容易地看到，在遞迴呼叫期間，最初的輸入值會一直列印到滿足基準條件為止，因為方法呼叫正在被壓入堆疊。一旦滿足基準條件，遞迴呼叫就完成了，方法的結果從堆疊中彈出，這從輸出中可以明顯看出。

Java 遞迴示例

1. 使用遞迴計算階乘

階乘是一個數學表示式，它表示以下公式。

n! = n * (n-1)!

這類問題非常適合使用遞迴來解決。考慮以下程式碼片段。

fact(n) = n * fact(n-1)

這裡有一個 fact() 方法，它將返回給定自然數的階乘。現在在實現 fact() 之前，我們應該很好地考慮基準條件，基準條件如下。

1! = 1

現在讓我們看看使用遞迴計算階乘的完整示例。

package com.tutorialspoint;

public class Tester {
   public static void main(String[] args) {
      Tester tester = new Tester();
      // call the recursive method to get the factorial
      int result = tester.fact(5);
      System.out.println("Factorial: " + result);
   }
   // recursive method
   public int fact(int n) {
      // if base condition is not true, make a recursive call
      return n == 1 ? 1: n * fact(n-1);
   }
}

輸出

讓我們編譯並執行上述程式，這將產生以下結果：

Factorial: 120

2. 使用遞迴計算斐波那契數列的和

斐波那契數列是數學中一個非常重要且有趣的數列。它表示以下等式：

F(n) = F(n-1) + F(n-2)

在這裡，我們可以說，斐波那契數表示其前一個數和次前一個數的和。斐波那契數列的形式是 0, 1, 1, 2, 3, 5 等等。

使用遞迴，我們可以很容易地計算斐波那契數。考慮以下程式碼片段。

fibo(n) = fibo(n-1) + fibo(n-2)

這裡有一個 fibo() 方法，它將返回給定整數的斐波那契數。現在在實現 fibo() 之前，我們應該很好地考慮基準條件，基準條件如下。

fibo(0) = 0;
fibo(1) = 1;

現在讓我們看看使用遞迴計算斐波那契數的完整示例。

package com.tutorialspoint;

public class Tester {
   public static void main(String[] args) {
      Tester tester = new Tester();
      int result = tester.fibo(5);
      System.out.println("Fibbonacci: " + result);
   }

   public int fibo(int n) {
      return n <= 1 ? n : fibo(n-1) + fibo(n-2);
   }
}

輸出

讓我們編譯並執行上述程式，這將產生以下結果：

Fibbonacci: 5

在 Java 中使用遞迴的優點

以下是 Java 中使用遞迴的優點：

• 更簡潔的程式碼 使用遞迴使程式碼易於理解並保持程式碼簡潔。與其使用多個 if 和迴圈條件，遞迴有助於以函式式方式編寫程式碼。
• 遞迴演算法 對於某些問題，例如樹遍歷、漢諾塔問題等，遞迴是編碼解決方案的最佳方法。
• 減少時間複雜度 遞迴程式有助於減少在大型資料集上搜索所需的時間。

在 Java 中使用遞迴的缺點

以下是 Java 中使用遞迴的缺點：

• 專業知識 儘管遞迴是一種更簡潔的方法，但它需要高度的專業知識和對問題陳述和擬議解決方案的理解。不正確地實現遞迴可能會導致效能問題，並且可能難以除錯。
• 記憶體空間密集 由於涉及多個函式呼叫和返回流，遞迴程式通常是記憶體密集型的。