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 中使用递归的缺点：

• 专业知识 尽管递归是一种更简洁的方法，但它需要高度的专业知识和对问题陈述和拟议解决方案的理解。不正确地实现递归可能会导致性能问题，并且可能难以调试。
• 内存空间密集 由于涉及多个函数调用和返回流，递归程序通常是内存密集型的。