Может кто-нибудь объяснить, пожалуйста, алгоритм обратной строки с использованием хвостовой рекурсии?

Question

Прошу прощения за глупость задавать этот вопрос. Я могу понять код до тех пор, пока не получу последний символ заданной строки и не вернусь, тогда я не могу связать логику рекурсии.

Прежде чем опубликовать это здесь, отладчик помог мне частично. К сожалению, не 100%

Не могли бы вы помочь мне понять это?

public static void main(String[] args) {
    System.out.println(reverseRecursively("abcd"));
}

public static String reverseRecursively(String str) {
    if (str.length() < 2) {
        return str;
    }
    return reverseRecursively(str.substring(1)) + str.charAt(0);
}

Вывод отладчика:

0=abcd
1=bcd
2=cd
3=d
Final: dcba

Answer 1

`public static String reverseRecursively(String str) {
    if (str.length() < 2) {
        return str;
    }
    return reverseRecursively(str.substring(1)) //take "bcd" : 1st Itration
                                                //"cd" : 2nd 
                                                // "d" : 3rd (this makes str.length() < 2)
 // 3rd returns first with "d" and pass control back to 2nd recursion
 //2nd takes d and adds 0th char c and returns with "dc" and pass control to 1st
 //1st takes dc and adds b returns with "dcb" and pass control to base call
 // base call take "dcb" and adds 0th char a and returns to calling method
+ str.charAt(0);
}`. 

Answer 2

Когда метод запускается, он сначала проверит, имеет ли длина строка один или ноль символов. Это скажет это, является ли это последним символом в строке. Если нет, он добавит текущий символ в конец строки и запустится снова, на этот раз для следующего следующего символа. Это означает, что строка каждый раз становится короче.

Что может сбить с толку, так это то, что str.charAt(0) не передается в следующую итерацию метода, а просто добавляется как часть оператора return. Это означает, что как только метод завершит выполнение последнего символа, он вернет все символы в обратном порядке, поскольку каждый метод завершает один за другим, начиная с того, который возвращает последний символ. Это будет происходить до тех пор, пока все методы не вернутся и не вернут вашу обратную строку.

Это как слои методов, один вызовет другой, а затем все они будут завершены в обратном порядке в том порядке, в котором они были вызваны.

Надеюсь, это помогло вашему пониманию!

Answer 3

Нет вопросов, это глупый вопрос. Если человек не задает вопрос, думая, что люди сочтут его глупым, значит, он глуп на всю жизнь. :)

Теперь объяснение:

Я добавил заявление для печати, чтобы помочь вам с этим.

public static String reverseRecursively(String str) {
    System.out.println("For debuging : "+str); // this is my print statement.
    if (str.length() < 2) {
        return str;
    }
    return reverseRecursively(str.substring(1)) + str.charAt(0);
}

Это печатает ниже.

    For debuging : abcd
    For debuging : bcd
    For debuging : cd
    For debuging : d
    dcba

Базовые критерии для метода, возвращающего значение: str.length() < 2.

Таким образом, когда "d" возвращается последним вызовом метода (или мы можем сказать, что четвертый вызов метода reverseRecursively(String str)), потому что длина меньше 2. Третий вызов метода вернет

"d" + "cd".charAt(0);

что является ничем иным, как: dc.

Similary 2 метод будет использовать возвращаемое значение третьего метода (DC) и вернет значение

"dc" + "bcd".charAt(0);

который является dcb.

и поэтому первый вызов метода, в котором вы передали строку "abcd" в качестве ввода, вернется.

"dcb" + "abcd".charAt(0);

который является dcba.

Надеюсь, это поможет. Ура !!!

Answer 4

Ну, это довольно простая логика:

return reverseRecursively(str.substring(1)) + str.charAt(0);

Если вы поместите System.out.println () перед возвратом, вы получите следующий вывод:

Recursing with substring: bcd and adding a
Recursing with substring: cd and adding b
Recursing with substring: d and adding c
Adding d as final char

Если вы измените это, вы получите dcba.

Почему это наоборот?

Ну, вы должны подумать о трассировке вызова:

return reverseRecursively("bcd") + a -> retruns "dcba"
-> return reverseRecursively("cd") + b -> returns "dcb"
 -> return reverseRecursively("d") + c -> returns "dc"
   -> return d -> returns "d"

Полагаю, ключевым моментом является понимание того, что рекурсия всегда сочетается с результатом другой рекурсии.