Java 简明教程
Java - Recursion
Java - Recursion
递归是一种编程技术，其中 method 调用自身来执行必要的子操作。调用自身的方法被称为递归函数。递归主要用于将大问题拆解成多个小问题，然后递归求解这些小问题。递归技术使得代码更易于阅读和理解。
Example
考虑以下情况 −
// 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);
}如果我们使用负 int 值调用此函数，则它将导致堆栈溢出错误。
How Recursion Works in Java?
在 Java 中，当发生 variables 、方法调用、引用时，它们会被存储在堆栈中，而对象会在堆中分配内存。每当调用方法时，它的详细信息都会被推入堆栈，比如传递的参数值、任何局部变量、计算等。在递归调用期间，每当方法调用自身，它的入口就会被推入堆栈，直到基本条件终止该流程。基本条件为真时，方法开始返回该值，子调用的结果会从堆栈中弹出，以此类推，直至该方法的全部入口从堆栈中弹出。让我们通过一个示例来理解这一点。
Example
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 Recursion Examples
1. Calculating Factorial Using Recursion
阶乘是一个表示以下公式的数学表达式。
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: 1202. Calculating Sum of Fibonacci Series Using Recursion
斐波那契数列是数学中非常重要而有趣的数列。它表示以下方程 −
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