Java 简明教程
Java - Recursion
Java - Recursion
递归是一种编程技术,其中 method 调用自身来执行必要的子操作。调用自身的方法被称为递归函数。递归主要用于将大问题拆解成多个小问题,然后递归求解这些小问题。递归技术使得代码更易于阅读和理解。
Recursion is a programming technique where a method calls itself to perform a sub-operation as necessary. The method which is calling itself is termed as a recursive function. Recursion is primary used to break big problems into smaller problems and then solving them recursively. Recursion technique makes code more readable and expressive.
Example
考虑以下情况 −
Consider the following case −
// 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 相加,得到所需结果。
In this case, we’re getting sum of n natural numbers using recursion which can be tabulated as n + sum of n - 1 numbers. Using recursion, we are adding the result of sum of n-1 natural numbers with n to get the required result.
由于递归函数调用自身,因此必须有一个基本条件,基于此条件,递归方法可以停止无限调用自身。如果基本条件不存在或永远不会为真,那么它将导致程序中的堆栈溢出。在上述示例中,我们有一个基本条件 n 为 1。
As a recursive function calls itself, there must be a base condition based on which the recursive method can stop calling itself indefinitely. If base condition is not present or never comes true, then it will cause a stack overflow in program. In above example, we’re having a base condition of n being 1.
public int sum(int n){
// base condition
if(n == 1){
return 1;
}
// recursive call
return n + sum(n-1);
}
如果我们使用负 int 值调用此函数,则它将导致堆栈溢出错误。
If we call this function with a negative int value, then it will cause a stack overflow error.
How Recursion Works in Java?
在 Java 中,当发生 variables 、方法调用、引用时,它们会被存储在堆栈中,而对象会在堆中分配内存。每当调用方法时,它的详细信息都会被推入堆栈,比如传递的参数值、任何局部变量、计算等。在递归调用期间,每当方法调用自身,它的入口就会被推入堆栈,直到基本条件终止该流程。基本条件为真时,方法开始返回该值,子调用的结果会从堆栈中弹出,以此类推,直至该方法的全部入口从堆栈中弹出。让我们通过一个示例来理解这一点。
In Java, variables, method call, references are stored in stack whereas objects are allotted memory in heap. Whenever a method is called, its details are pushed to the stack like value of the argument passed, any local variable, computation etc. During recursive call, whenever a method calls itself, its entry is pushed to the stack till the base condition terminates the flow. When base condition comes true, and method starts returning the value, the result of sub call is popped from the stack and so on till the all entries of method is popped from the stack. Let’s understand this with an example.
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;
}
}
让我们编译并运行上述程序,这将生成以下结果 −
Let us compile and run the above program, this will produce the following 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
在此程序中,我们可以很容易地看出,在递归调用期间,最初输入的值会一直打印,直到满足基本条件,因为方法调用正在被推送到堆栈。一旦满足了基本条件,递归调用结束,方法结果从堆栈弹出,这从输出中可以明显看出。
In this program, we can see easily that during recursive calls, initially input value is getting printed till the base condition is fulfilled as method calls are being pushed to stack. Once base condition is fulfilled, the recursive calls finished and method result is getting popped from the stack as evident from the output.
Java Recursion Examples
1. Calculating Factorial Using Recursion
阶乘是一个表示以下公式的数学表达式。
factorial is a mathematical expression which represents the following formulation.
n! = n * (n-1)!
这类问题非常适合使用递归来解决。考虑以下代码片段。
This kind of the problems are perfect candidates to be solved using recursion. Consider the following code snippet.
fact(n) = n * fact(n-1)
这里,fact() 是一个方法,用于返回给定的自然数的阶乘。现在在实现 fact() 之前,我们应该考虑哪些基本条件是正确的。它们应该是以下条件。
Here a fact() is method which is to return the factorial of a given natural number. Now before implementing the fact(), we should think on base conditions are well which should be as following.
1! = 1
现在让我们看看使用递归计算阶乘的完整示例。
Now let’s see the complete example for factorial using recursion.
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);
}
}
让我们编译并运行上述程序,这将生成以下结果 −
Let us compile and run the above program, this will produce the following result −
Factorial: 120
2. Calculating Sum of Fibonacci Series Using Recursion
斐波那契数列是数学中非常重要而有趣的数列。它表示以下方程 −
fibbonacci series is a very important and interesting series in mathematics. It represents the follwing equation −
F(n) = F(n-1) + F(n-2)
在这里,我们可以说,斐波那契数表示其前一个数和前前一个数的和。斐波那契数列的形式为 0、1、1、2、3、5,依此类推。
Here, we cand say, fibbonacci number represents the sum of its predecessor and the next predecessor. A fibbonacci series is of form 0, 1, 1, 2, 3, 5 and s on.
使用递归,我们可以轻松计算斐波那契数。考虑以下代码片段。
Using recursion, we can easily compute the fibbonacci number. Consider the following code snippet.
fibo(n) = fibo(n-1) + fibo(n-2)
这里,fibo() 是一个方法,用于返回给定的整数的斐波那契数。现在在实现 fibo() 之前,我们应该考虑哪些基本条件是正确的。它们应该是以下条件。
Here a fibo() is method which is to return the fibonacci of a given whole number. Now before implementing the fibo(), we should think on base conditions are well which should be as following.
fibo(0) = 0;
fibo(1) = 1;
现在让我们看看使用递归计算斐波那契数的完整示例。
Now let’s see the complete example for fibonacci number computation using recursion.
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);
}
}
让我们编译并运行上述程序,这将生成以下结果 −
Let us compile and run the above program, this will produce the following result −
Fibbonacci: 5
Advantages of Using Recursion in Java
在 Java 中使用递归有以下优点:
Following are the advantages of using recursion in Java:
-
Cleaner code Using recursion makes code easy to understand and keeps code clean. Instead of using multiple if and loops conditions, recursion helps in writing code in functional way.
-
Recursive algorithm For certain problem, like tree traversal, tower of hanoi problem etc, recursion is the best apporach to code the solution.
-
Reduces time complexity Recursive program helps in reducing time taken in searches on large datasets.
Disadvantages of Using Recursion in Java
在 Java 中使用递归有以下缺点:
Following are the disadvantages of using recursion in Java:
-
Expertise Recursion although is a cleaner approach but required high amount of expertise and understanding of the problem statement and proposed solution. An incorrectly implemented recursion may cause performance issues and may be hard to debug.
-
Memory space intensive Being multiple function calls involved and return flows, recursive programs are generally memory intensive.