递归是一种编程技巧，其中方法通过自我调用来执行必要的子操作。调用自身的函数称为递归函数。递归主要用于将大问题分解为较小的问题，然后递归地解决这些问题。递归技术使代码更具可读性和表达力。
示例
考虑以下情况：
public int sum(int n){
return n == 1 ? 1 : n + sum(n-1);
}
在这个例子中，我们使用递归来获取自然数的和，这可以表示为 n 加上 n-1 数字的和。通过递归，我们将 n-1 自然数的和的结果与 n 相加以得到所需的结果。
由于递归函数会调用自身，因此必须有一个基本条件来终止递归方法无限调用自身。如果没有基本条件或基本条件永远不会成立，则会导致栈溢出。在上面的例子中，我们有一个 n 为 1 的基本条件。
public int sum(int n){
if(n == 1){
return 1;
}
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;
if(n == 1){
result = 1;
System.out.println("Base condition fulfilled.");
}else {
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();
int result = tester.fact(5);
System.out.println("Factorial: " + result);
}
public int fact(int n) {
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 中使用递归的优点
-
更清晰的代码：使用递归可以使代码易于理解并保持代码整洁。相对于使用多个 if 和循环条件，递归有助于以函数的方式编写代码。
-
递归算法：对于某些问题，如树遍历、汉诺塔问题等，递归是最好的解决方案。
-
减少时间复杂度：递归程序有助于减少在大数据集上的搜索所需的时间。
在 Java 中使用递归的缺点
-
技术要求高：虽然递归是一种更干净的方法，但它需要高度的专业知识和对问题陈述及提议解决方案的理解。不正确实施的递归可能会引起性能问题，并且可能难以调试。
-
占用大量内存空间：由于涉及多次函数调用和返回流，递归程序通常占用大量内存。