Java 中的递归

2025年4月6日 | 阅读10分钟

Java 中的递归是指一个方法不断调用自身的过程。调用自身的方法称为递归方法。它是一个功能强大的概念，常用于算法和问题解决中。

它使代码紧凑，但理解起来更复杂。

语法

returntype methodname(){
//code to be executed
methodname();//calling same method
}

递归是如何工作的？

递归有两种情况：基本情况和递归情况，下面将对此进行讨论。

1) 基本情况

递归中的基本情况作为停止条件。它至关重要，因为没有它，递归函数会无限地调用自身，导致堆栈溢出错误。基本情况定义了递归何时应该停止。

2) 递归情况

递归情况是函数调用自身并修改参数，向基本情况推进的地方。函数的这一部分不断缩小问题规模，直到达到基本情况。

Java 中的递归程序：前 N 个自然数的和

考虑最简单的递归函数，计算前 N 个自然数的和

示例

class SumExample {  
    // Recursive function to calculate the sum of first 'n' natural numbers  
    public static int sum(int n) {  
        // Base case: If n is 0, return 0 (base case)  
        if (n == 0)  
            return 0;  
        else  
            return n + sum(n - 1); // Recursive case: If n is not 0, recursively call the sum function with n-1 and add it to n 
    }  
}
public class Main{
 public static void main(String[] args) {  
    int num = 5; // Number of natural numbers to sum  
    // Calculate sum of first 'num' natural numbers using recursive sum function  
    int result = SumExample.sum(num);
    // Print the result  
    System.out.println("Sum of first " + num + " natural numbers is: " + result);  
 }  
}  

编译并运行

输出

Sum of first 5 natural numbers is: 15

在此示例中，if (n == 0) 是基本情况。当 n 变为 0 时，递归停止。

递归程序：无限次

示例

class RecursionExample {
    // Recursive function p() which prints "hello" and calls itself indefinitely
    static void p() {
        System.out.println("hello"); // Print "hello"
        p(); // Recursive call to itself
    }
}
public class Main{
    public static void main(String[] args) {
        RecursionExample.p(); // Initial call to p() from the main method
    }
}

输出

hello
hello
...
java.lang.StackOverflowError

Java 递归程序：有限次

示例

class RecursionExample {  
    static int count = 0; // Static variable to keep track of the count  
    // Recursive method p() which increments count, prints "hello" along with the count, and calls itself recursively  
    static void p() {  
        count++; // Increment the count  
        // Check if count is less than or equal to 5  
        if (count <= 5) {  
            System.out.println("hello " + count); // Print "hello" along with the current count  
            p(); // Recursive call to itself  
        }  
    }  
}
public class Main{
    public static void main(String[] args) {  
        RecursionExample.p(); // Initial call to the p() method from the main method  
    }  
}

编译并运行

输出

hello 1
hello 2
hello 3
hello 4
hello 5

Java 中使用递归的阶乘

让我们看一个使用递归计算阶乘的例子

示例

class FactorialExample {  
    // Recursive function to calculate the factorial of a non-negative integer 'n'  
    public static int factorial(int n) {  
        // Base case: If n is 0 or 1, factorial is 1  
        if (n == 0 || n == 1)  
            return 1;  
        // Recursive case: If n is greater than 1, recursively call factorial function with n-1 and multiply it with n  
        else  
            return n * factorial(n - 1);  
    }  
}
public class Main{
    public static void main(String[] args) {  
        int num = 5; // Number for which factorial is to be calculated  
        // Calculate factorial of 'num' using recursive factorial function  
        int result = FactorialExample.factorial(num);  
        // Print the result  
        System.out.println("Factorial of " + num + " is: " + result);  
    }  
}  

编译并运行

输出

Factorial of 5 is: 120

上述程序的工作原理

factorial(5) 
   factorial(4) 
      factorial(3) 
         factorial(2) 
            factorial(1) 
               return 1 
            return 2*1 = 2 
         return 3*2 = 6 
      return 4*6 = 24 
   return 5*24 = 120

Java 中使用递归的斐波那契数列

我们可以使用递归在 Java 中创建一个斐波那契数列程序。

示例

class F{  
    static int n1=0,n2=1,n3=0;      
     static void printFibo(int count){      
        if(count>0){      
             n3 = n1 + n2;      
             n1 = n2;      
             n2 = n3;      
             System.out.print(" "+n3);     
             printFibo(count-1);      
         }      
     }        
}
public class Main{
 public static void main(String[] args) {  
    int count=15;      
    System.out.print(F.n1+" "+F.n2);//printing 0 and 1      
    F.printFibo(count-2);//n-2 because 2 numbers are already printed     
 }  
}  

编译并运行

输出

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

堆栈溢出错误

“堆栈溢出”错误是当程序由于过度递归耗尽其调用堆栈时发生的运行时错误。此错误通常发生在递归函数没有适当的终止条件或递归深度变得太大时。

如果您尝试计算一个非常大的数字的阶乘，您可能会遇到堆栈溢出错误，因为递归深度变得太深。例如，如果您尝试计算负数或非常大的正数的阶乘，可能会导致堆栈溢出错误。

为了克服上述错误，请遵循以下规则

确保正确的基准情况：确保您的递归函数有一个正确的基准情况，最终将终止递归。在阶乘示例中，基准情况是 n 为 0 或 1。

限制递归深度：如果可能，限制最大递归深度，或者对于递归深度可能过大的情况使用迭代方法。

优化递归：有时，我们可以优化递归算法以减少递归深度或使用尾递归，某些编译器可以将其优化为迭代形式。

例如，这是阶乘函数，并带有额外的检查以防止负数

示例

class FactorialExample {  
    // Recursive function to calculate the factorial of a non-negative integer 'n'  
    public static int factorial(int n) {  
        // Base case: if n is negative, return an error code  
        if (n < 0)  
            return -1; // Error code for invalid input  
        // Base case: if n is 0 or 1, factorial is 1  
        else if (n == 0 || n == 1)  
            return 1;  
        // Recursive case: if n is greater than 1, recursively call factorial function with n-1 and multiply it with n  
        else  
            return n * factorial(n - 1);  
    }  
}
public class Main{
    public static void main(String[] args) {  
        int num = 5; // Number for which factorial is to be calculated  
        // Calculate factorial of 'num' using recursive factorial function  
        int result = FactorialExample.factorial(num);  
        // Print the result  
        System.out.println("Factorial of " + num + " is: " + result);  
    }  
}  

编译并运行

输出

Factorial of 5 is: 120

递归期间内存是如何分配给各种函数调用的？

在递归中，内存是分配给程序调用栈上的函数调用的。每次调用函数时，都会创建一个新的栈帧并将其推入调用栈。此栈帧包含函数参数、局部变量、返回地址以及执行函数所需的其他必要数据。

当函数返回时，其栈帧会从调用栈中弹出，释放分配给它的内存。这个过程一直持续到初始函数调用（通常是 Java 中的 main()）完成，此时调用栈变为空。

让我们分解一下递归期间内存分配的工作原理

初始函数调用

当函数第一次被调用时，其参数和局部变量会在一个栈帧中分配内存。
返回地址（指示函数完成后的返回位置）也存储在栈帧中。
如果函数递归调用自身，则为每个递归调用创建一个新的栈帧。

递归调用

每次递归调用都会导致创建新的栈帧。
每个递归调用的参数和局部变量都存储在其各自的栈帧中。
随着递归的进行，调用栈会变得越来越深，每个函数调用都会在前一个栈帧之上添加一个新的栈帧。

基本情况和返回

当达到基本情况（即递归的终止条件）时，函数开始返回。
当每个函数返回时，其栈帧会从调用栈中弹出，释放分配给它的内存。
每个函数调用的返回值通常用于计算前一个函数调用的结果，直到初始函数调用返回最终结果。

Stack Overflow

如果递归深度变得太大，调用堆栈可能会耗尽内存，从而导致堆栈溢出错误。
这通常发生在嵌套函数调用过多且调用堆栈超出其最大大小时。

示例：FactorialExample.java

public class FactorialExample {
    public static int factorial(int n) {
        // Base case
        if (n == 0 || n == 1)
            return 1;
        // Recursive case
        else
            return n * factorial(n - 1);
    }
    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println("Factorial of 5 is: " + result);
    }
}

输出

Factorial of 5 is: 120

说明

在此示例中，当调用 factorial(5) 时

初始调用 (factorial(5))

为对 factorial(5) 的初始调用创建栈帧。
在此栈帧内部，n 的值设置为 5，并存储了其他必要信息，例如返回地址。

第一次递归调用 (factorial(4))

遇到递归调用 factorial(n - 1) 时，为 factorial(4) 创建新的栈帧。
此栈帧包含其自己的参数 n 的副本，该副本设置为 4。
调用栈现在包含两个栈帧：一个用于 factorial(5)，一个用于 factorial(4)。

后续递归调用

随着更多的递归调用，该过程重复，每个调用都会创建一个新的栈帧，其中包含其自己的参数 n 的副本。
每个栈帧都保留在调用栈上，直到其对应的函数调用完成。

基本情况和返回

最终，达到基本情况 (n == 0 或 n == 1)，递归开始展开。
当每个函数调用返回时，其栈帧会从调用栈中移除，从而释放内存。
递归调用的返回值用于计算最终结果。

最终结果

所有递归调用返回后，对 factorial(5) 的初始调用将获得最终结果。
一旦 main 函数完成，调用栈变为空，所有分配给函数调用的内存都被释放。

递归编程的优点

简洁和清晰：递归解决方案通常比迭代解决方案更简洁，更容易理解。它们反映了问题的自然结构，使代码直观且易读。

分而治之：递归算法遵循分而治之的范式，将复杂问题分解为更小、更易于管理的问题。这简化了问题解决并产生了优雅的解决方案。

模块化：递归函数封装了重复模式，促进了代码重用。一旦实现了递归函数，它就可以轻松地重用于类似的问题而无需修改。

降低代码复杂度：递归解决方案可以通过抽象重复细节来降低代码复杂度。与等效的迭代解决方案相比，它们通常导致更少的代码行，从而产生更清晰、更易于维护的代码库。

支持数据结构：递归非常适合解决涉及树状数据结构（如二叉树、图和链表）的问题。它简化了这些数据结构的遍历、搜索和操作等操作。

数学问题：递归编程对于解决具有递归模式的数学问题特别有效，例如阶乘计算、斐波那契数列生成和幂运算。

并行性和并发性：递归算法可以并行化以利用多核处理器和分布式计算环境。每个递归分支可以并发执行，在某些情况下提高了性能。

递归编程的缺点

性能开销：递归解决方案通常会由于额外的函数调用堆栈管理而产生性能开销。每次递归调用都需要为参数、局部变量和返回地址分配内存，这可能导致内存使用增加和执行速度变慢，与迭代解决方案相比。

堆栈溢出：过度递归可能导致堆栈溢出错误，特别是当递归深度变得太大时。当调用堆栈由于大量嵌套函数调用而耗尽内存时，就会发生这种情况，导致程序意外终止。

调试困难：与迭代解决方案相比，递归解决方案可能更难调试。通过多个递归调用来识别逻辑错误或意外行为可能需要额外的努力和调试工具。

无限递归的可能性：如果递归函数缺乏适当的终止条件，或者终止条件未正确实现，则可能导致无限递归。无限递归会导致程序进入无限循环，消耗 CPU 资源并可能使程序崩溃。

对某些开发人员来说可读性有限：虽然递归解决方案可以简洁优雅，但对于所有开发人员来说，尤其是那些不熟悉递归编程概念的开发人员来说，它们可能不那么容易理解。理解执行流和推理递归算法可能需要一些程序员付出额外的努力。

优化困难：与迭代算法相比，递归算法可能更难优化。尾递归优化和记忆化技术可能有助于提高性能，但优化递归解决方案通常需要对问题领域和底层递归模式有深入的理解。

潜在的糟糕可伸缩性：递归算法可能无法很好地扩展到非常大的输入大小或深度嵌套的数据结构。与递归函数调用和内存分配相关的开销对于极其庞大的问题实例可能变得过高，从而导致性能下降或资源耗尽。

下一主题Java-枚举

Java 中的递归

递归是如何工作的？

1) 基本情况

2) 递归情况

Java 中的递归程序：前 N 个自然数的和

示例

递归程序：无限次

示例

Java 递归程序：有限次

示例

Java 中使用递归的阶乘

示例

Java 中使用递归的斐波那契数列

示例

堆栈溢出错误

示例

递归期间内存是如何分配给各种函数调用的？

递归编程的优点

递归编程的缺点

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 教程

控制语句

Java Object 类

Java 继承

Java 多态

Java 抽象

Java 封装

Java 数组

Java OOPs 杂项

Java 字符串

Java 正则表达式

异常处理

Java 内部类

Java 多线程

Java 同步

Java I/O

Java 文件处理

Java 序列化

Java 网络

Java 反射

Java 集合

Java 5 特性

Java 8 特性

Java JDBC

RMI

国际化

Java 项目

Java 中的递归

递归是如何工作的？

1) 基本情况

2) 递归情况

Java 中的递归程序：前 N 个自然数的和

示例

递归程序：无限次

示例

Java 递归程序：有限次

示例

Java 中使用递归的阶乘

示例

Java 中使用递归的斐波那契数列

示例

堆栈溢出错误

示例

递归期间内存是如何分配给各种函数调用的？

递归编程的优点

递归编程的缺点

相关帖子

Java 中的对象克隆 | clone() 方法

Java 命令行参数

Java 包装类

Java 中的动态方法分派

Java Math 类（带示例的方法）

Java 中的值传递和引用传递

Java 中的 Object 类

Java 中类和接口的区别

Java 中方法重载和方法重写的区别

Java 中的编译时多态

订阅 Tpoint Tech

联系信息

关注我们