如何使用递归在 Java 中反转字符串

2025年3月17日 | 阅读 3 分钟

Java 中的递归是指一个函数/方法不断调用自身的过程。在编程语言中，如果一个程序允许我们在同一个方法名内调用一个方法，则称为递归调用。它使代码更简洁，但理解起来具有挑战性。它用于解决可以将复杂问题分解为更小、重复性问题的问题。利用递归，我们可以解决许多复杂的问题，例如阶乘程序、斐波那契数列、汉诺塔等。

方法论

首先，从字符串中移除第一个元素/字符，然后将该元素/字符附加到字符串的末尾。
重复上述步骤，直到输入字符串变为 null。

StringReverse.java

// Java Program to Reverse a String using recursion
// importing the required packages
import java.io.*;
import java.util.*;
class StringReverse {
    // This method is used to reverse a string using stack
	public static String reverseString(String str)
	{
        // Recursive method for revarsinga a string
        if(str.isEmpty())  
            {  
                // If the string satisfy the above condition we simply return the same string
                return str;  
            }   
            else   
            {  
                return reverseString(str.substring(1))+str.charAt(0);  
            }  
	}
	// Driver code
	public static void main(String[] args)
	{
	    System.out.println(" Hello, World! ");
	    // Creating an object to the Scanner class such that we can take the inputs from the user
	    Scanner sc = new Scanner(System.in);
	    System.out.println(" Enter a String: ");
	    // reading the String
	    String str = sc.next();
	    // printing the string
	    System.out.println(" The entered String is: " + str);
	    // printing the reverse String
	    System.out.println(" The String in reverse order is: " + reverseString(str));
	}
}

输出

How to reverse a string using recursion in Java

解释

在上面的程序中，我们创建了一个名为 reverseString() 的方法。它会解析我们的字符串是否为 null。如果字符串为空，则返回相同的字符串。我们使用了 String 类的以下两个方法

时间复杂度：O(n^2)

O(n^2) 因为 substr() 的时间复杂度为 O(k)，其中 k 是返回的字符串的大小。因此，对于每次递归调用，我们将字符串的大小减一，这会导致一个类似 (k-1)+(k-2)+… +1 = k*(k-1)/2 = O(k^2) = O(n^2) 的级数

空间复杂度：O(n)

其中 n 是字符串的大小。

高效方法

我们可以将每个字符存储在递归堆栈中，然后可以在返回时打印，如下面的代码所示。

// Java Program to Reverse a String using recursion
// importing the required packages
import java.io.*;
import java.util.*;
class ReverseString {
    static void stringReverse(String str, int index, int n)
    {
        // returns to the method if the index has reached at the end of the string
        if (index == n) 
        {
            return;
        }
        char temp = str.charAt(index); // storing away each character beginning from index 0 in method call stack;
        stringReverse(str, index + 1, n); //raising index when every time when running a recursive function
        System.out.print(temp); // printing each stored character while recurring back
  }
	// Driver code
	public static void main(String[] args)
	{
	    System.out.println(" Hello, World! ");
	    // Creating an object to the Scanner class such that we can take the inputs from the user
	    Scanner sc = new Scanner(System.in);
	    System.out.println(" Enter a String: ");
	    // reading the String
	    String str = sc.next();
	    // printing the string
	    System.out.println(" The entered String is: " + str);
	    int n = str.length();
	    // printing the reverse String
	    System.out.println(" The String in reverse order is: ");
	    stringReverse(str, 0, n);
	}
}

输出

时间复杂度： O(n)，其中 n 是字符串的大小

空间复杂度： O(n)，其中 n 是字符串的大小

下一主题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 Conversion

Java Misc

如何使用递归在 Java 中反转字符串

方法论

高效方法

相关帖子

Java 中的皇冠图案

Java ArrayList 内部工作原理

Java Integer getInteger() Method

POJO

Java Agent Programming

Strontio Number in Java

Java 中 Jdeps 和 Jdeprscan 工具的区别

Java Image

为什么在 Java 中使用泛型

Linked List Intersection at End Using Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器