用 Java 進行函數語言程式設計 - 遞迴

遞迴是在滿足特定條件之前在一個函式中呼叫同一函式。它有助於將大問題分解成小問題。遞迴還使程式碼更易於閱讀和表達。

命令式與遞迴

以下示例顯示了同時使用這兩種技術計算自然數總和。

public class FunctionTester {
   public static void main(String[] args) {
      System.out.println("Sum using imperative way. Sum(5) : " + sum(5));
      System.out.println("Sum using recursive way. Sum(5) : " + sumRecursive(5));
   }

   private static int sum(int n){
      int result = 0;
      for(int i = 1; i <= n; i++){
         result = result + i;
      }
      return result;
   }

   private static int sumRecursive(int n){
      if(n == 1){
         return 1;
      }else{
         return n + sumRecursive(n-1);
      }
   }
}

輸出

Sum using imperative way. Sum(5) : 15
Sum using recursive way. Sum(5) : 15

使用遞迴，我們將 n-1 個自然數的和的結果與 n 相加，從而獲得所需的結果。

尾遞迴

尾遞迴表示遞迴方法呼叫應在最後進行。以下示例顯示了使用尾遞迴列印數字序列。

public class FunctionTester {
   public static void main(String[] args) {
      printUsingTailRecursion(5);
   }

   public static void printUsingTailRecursion(int n){
      if(n == 0) 
         return;
      else
         System.out.println(n);
      printUsingTailRecursion(n-1);
   }
}

輸出

5
4
3
2
1

頭遞迴

頭遞迴表示遞迴方法呼叫應在程式碼開頭進行。以下示例顯示了使用頭遞迴列印數字序列。

public class FunctionTester {
   public static void main(String[] args) {     
      printUsingHeadRecursion(5);
   }

   public static void printUsingHeadRecursion(int n){
      if(n == 0) 
         return;
      else
         printUsingHeadRecursion(n-1); 
      System.out.println(n);
   }
}

輸出

1
2
3
4
5