Сторнирование строки с помощью рекурсии в Java

Question

Вот некоторый Java-код для рекурсивного изменения строки.

Может ли кто-нибудь объяснить, как это работает?

public static String reverse(String str) {
    if ((null == str) || (str.length() <= 1)) {
        return str;
    }
    return reverse(str.substring(1)) + str.charAt(0);
}

Я не понимаю, как это может работать.

Answer 1

Функция берет первый символ строки - str.charAt(0) - ставит его в конец, а затем вызывает себя - reverse() - для остатка - str.substring(1), складывая эти две вещи вместе, чтобы получить результат - reverse(str.substring(1)) + str.charAt(0)

Когда переданный в String является одним символом или меньше, и поэтому не останется никакого остатка - когда str.length() <= 1) - он прекращает вызывать себя рекурсивно и просто возвращает переданную String.

Так это работает следующим образом:

reverse("Hello")
(reverse("ello")) + "H"
((reverse("llo")) + "e") + "H"
(((reverse("lo")) + "l") + "e") + "H"
((((reverse("o")) + "l") + "l") + "e") + "H"
(((("o") + "l") + "l") + "e") + "H"
"olleH"

Answer 2

Вы должны помнить, что у вас не будет просто одного вызова - у вас будет вложенных вызовов. Таким образом, когда «наиболее высоко вложенный» вызов немедленно возвращается (когда он находит только «o»), следующий уровень вверх займет str.charAt(0) - где str - это «lo» в этой точке. Так что вернусь "ол".

Затем уровень next получит "ol", выполните str.charAt(0) для его значение str (что означает "llo"), возвращая "oll" в следующий уровень.

Тогда уровень next получит «oll» от своего рекурсивного вызова, выполняя str.charAt(0) для его значение str (что означает «ello»), возвращая "olle" на следующий уровень.

Тогда уровень final получит «oll» от своего рекурсивного вызова, выполняя str.charAt(0) для его значение str (что «привет»), возвращая "olleh" для первоначального абонента.

Может иметь смысл думать о стеке по ходу дела:

// Most deeply nested call first...
reverse("o") -> returns "o"
reverse("lo") -> adds 'l', returns "ol" 
reverse("llo") -> adds 'l', returns "oll" 
reverse("ello") -> adds 'e', returns "olle" 
reverse("hello") -> adds 'h', returns "olleh" 

Answer 3

Запустите его через отладчик. Все станет ясно.

Answer 4

Встроенный образец;

public static String strrev(String str) {
    return !str.equals("") ? strrev(str.substring(1)) + str.charAt(0) : str;
}

Answer 5

Запустите приведенный ниже код - он печатает:

Шаг 0: ello / H
Шаг 1: llo / e
Шаг 2: lo / l
Шаг 3:o / l
Шаг 3 возвращает: ol
Шаг 2 возвращает: oll
Шаг 1 возвращает: olle
Шаг 0 возвращает: olleH

Код:

public class Test {

    private static int i = 0;

    public static void main(String args[]) {
        reverse("Hello");
    }

    public static String reverse(String str) {
        int localI = i++;
        if ((null == str) || (str.length()  <= 1)) {
            return str;
        }
        System.out.println("Step " + localI + ": " + str.substring(1) + " / " + str.charAt(0));
        String reversed = reverse(str.substring(1)) + str.charAt(0);

        System.out.println("Step " + localI + " returns: " + reversed);
        return reversed;
    }
}

Answer 6

Поскольку это рекурсивно, ваш вывод на каждом шаге будет выглядеть примерно так:

1. Введено «Привет». Затем метод вызывает себя с помощью «ello» и возвращает результат + «H»
2. Введено «ello». Метод вызывает себя с помощью «llo» и возвращает результат + «e»
3. Вводится "llo". Метод вызывает себя с помощью «lo» и возвращает результат + «l»
4. Введено «lo». Метод вызывает себя с помощью «o» и возвращает результат + «l»
5. Введено «o». Метод выполнит условие if и вернет "o"

Теперь перейдем к результатам:

Итоговое возвращаемое значение даст вам результат рекурсивного вызова плюс первый символ

К возврату из 5 будет: "o"

Возвращение от 4 будет: "o" + "l"

Возвращение от 3 будет: "ol" + "l"

Возвращение от 2 будет: "oll" + "e"

Возвращение от 1 будет: "olle" + "H"

Это даст вам результат "olleH"

Answer 7

import java.util.*;

public class StringReverser
{
   static Scanner keyboard = new Scanner(System.in);

   public static String getReverser(String in, int i)
   {
      if (i < 0)
         return "";
      else
         return in.charAt(i) + getReverser(in, i-1);
   }

   public static void main (String[] args)
   {
      int index = 0;

      System.out.println("Enter a String");
      String input = keyboard.nextLine();


      System.out.println(getReverser(input, input.length()-1));
   }
}

Answer 8

class Test {
   public static void main (String[] args){
      String input = "hello";
      System.out.println(reverse(input));
    }

    private static String reverse(String input) {
        if(input.equals("") || input == null) {
        return "";
    }
    return input.substring(input.length()-1) + reverse(input.substring(0, input.length()-1));
} }

Вот пример кода, который может вам помочь. Работал на меня.

Answer 9

import java.util.Scanner;

public class recursion{
    public static void main (String []args){

    Scanner scan = new Scanner(System.in);
    System.out.print("Input: ");
    String input = scan.nextLine();

    System.out.print("Reversed: ");
    System.out.println(reverseStringVariable(input));

    }public static String reverseStringVariable(String s) {
        String reverseStringVariable = "";

        for (int i = s.length() - 1; i != -1; i--) {
            reverseStringVariable += s.charAt(i);

        }

        return reverseStringVariable;
    }
}

Answer 10

Другие решения для обращения строки в Java.

Преобразование строки в массив символов с помощью функции .toCharArray ().

public static char[] reverse(char in[], int inLength, char out[],
            int tractOut) {

        if (inLength >= 0) {
            out[tractOut] = in[inLength];
            reverse(in, inLength - 1, out, tractOut + 1);
        }

        return null;

    }