Functional Programming With Java 简明教程

Functional Programming with Java - Recursion

递归是在函数中调用相同函数,直到满足特定条件。它有助于将大问题分解成小问题。递归还使代码更具可读性和表现力。

Imperative vs Recursive

以下示例展示了使用这两种技术计算自然数的总和。

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

Output

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

使用递归,我们通过将 n-1 个自然数的总和结果与 n 相加来获取所需结果。

Tail Recursion

尾递归是指递归方法调用应位于结尾。以下示例展示了使用尾递归打印数字序列。

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

Output

5
4
3
2
1

Head Recursion

头递归是指递归方法调用应位于代码的开头。以下示例展示了使用头递归打印数字序列。

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

Output

1
2
3
4
5