Может кто-нибудь провести меня через процесс рекурсии Java для этого кода?

Question

У меня возникли проблемы с пониманием процесса рекурсии для этого конкретного кода.

public static void testMethod(int n){

      if(n > 0){
         testMethod(n-1);
         System.out.print("A");
         testMethod(n-1);
         System.out.print("B");
      }
}

Например, если в моем основном методе я набираю

testMethod(2);

Выходные данныекод такой: ABAABB.

Я думаю, что этот код будет работать до тех пор, пока n=0 не пропустит оператор if, но выполнит всего 3 раза и выдаст ABкаждый раз. Понятно, что я не думаю об этом правильно.

Если бы кто-нибудь мог рассказать мне о том, почему это ABAABB, а не что-то вроде ABABAB, я был бы очень признателен!

Answer 1

Вы можете на самом деле пройти через эту визуализацию того, что n будет каждый шаг на этом пути.

Вероятно, наиболее важным моментом является то, что когда рекурсия попадает в 1-случай, она печатает " AB ", но даже если она не находится в 1-случае, она печатает A после первого вызова и B после второго вызова. Поэтому, когда мы вызываем 2, мы ожидаем 1-кейс (" AB "), затем " A " и затем 1-кейс (" AB * 1016"). * "), а затем" B". Или " ABAABB "

testMethod(2) {
--testMethod(1) {
----testMethod(0);
----System.out.print("A");
----testMethod(0);
----System.out.print("B");
--}
--System.out.print("A");
--testMethod(1) {
----testMethod(0);
----System.out.print("A");
----testMethod(0);
----System.out.print("B");
--}
-- System.out.print("B");
}

Если вы просматриваете отпечатки по порядку, имеет смысл получить этот вывод.

Answer 2

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

Для n = 2 полное дерево будет следующим:

Теперь вам нужно пройти по дереву слева направо (по порядку, только листья), вы получите:

print ("A ") печать (" B ") печать (" A ") печать (" A ") печать (" B ") печать (" B ")

, что: ABAABB

Answer 3

Итак, скажем, ваши строки кода:

public static void testMethod(int n) {
    if (n > 0) {
        testMethod(n - 1);       /* line1 */
        System.out.print("A");   /* line2 */
        testMethod(n - 1);       /* line3 */
        System.out.print("B");   /* line4 */
    }                            /* line5 */
}

Тогда у вас будут следующие шаги:

 1. n=2: line1 -> testMethod(n=1)
 2. n=1: line1 -> testMethod(n=0)
 3. n=0: line5 -> return
 4. n=1: line2 -> prints "A"
 5. n=1: line3 -> testMethod(n=0) 
 6. n=0: line5 -> return
 7. n=1: line4 -> prints "B"
 8. n=1: line5 -> return
 9. n=2: line2 -> prints "A"
10. n=2: line3 -> testMethod(n=1)
11. n=1: see 2-8
... n=1:          prints "AB"
18. n=2: line4 -> prints "B"
19. n=2: line5 -> return

Answer 4

Ключ должен помнить, что после вызова рекурсии все инструкции в этом дополнительном вызове выполняются до выполнения оставшихся инструкций в родительском элементе. И в вашем коде есть два рекурсивных вызова (n-1), по одному перед каждой печатью.

Давайте попробуем визуализировать стек вызовов для testMethod (2): n = 2> 0, затем основной стекis:

1. testMethod(1); // 2- 1
2. System.out.print("A");
3. testMethod(1); // 2 - 1
4. System.out.print("B");`

Теперь давайте рассмотрим подзвон testMethod (1) n = 1> 0, стек для testMethod (1);=>

testMethod(0); // 1-1
System.out.print("A");
testMethod(0); // 1 -1
System.out.print("B");`

С testMethod (0);ничего не делает (0 не> 0) мы можем удалить testMethod (0), чтобы упростить стек для testMethod (1);=>

System.out.print("A");
System.out.print("B");`

Теперь давайте заменим это обратно в основной стек для testMethod (2) =>

1.1 System.out.print("A");//-----
                                 //-----> testMethod(1)
1.2 System.out.print("B");`//----

2. System.out.print("A");

3.1 System.out.print("A");//-----
                                 //-----> second testMethod(1)
3.2 System.out.print("B");`//----

4. System.out.print("B");`

, который затем распечатывается в порядке ABAABB

Cheers!

Answer 5

Для иллюстрации давайте представим, что testMethod(n-1) печатает "-". Тогда testMethod(n) выведет "-AB".

Answer 6

Итак, сначала testMethod вызывается с 2 . Его проверка, если 2> 0 -> true

Теперь давайте скажем, чтобы сделать его более понятным testMethod1 вызывается с 1 Его проверка, если 1> 0 -> true

Теперь testMethod2 вызывается с 0 .

0> 0 -> false - этот вызов ничего не делает, поэтому обратно к testMethod1

testMethod1 печатает вызовы testMethod3 с 0 , поэтому ничего не происходит снова и возвращается к testMethod1 снова testMethod1 напечатайте B, и теперь мы возвращаемся к исходному testMethod call

A напечатано, и теперь мы снова делаем то же самое, так что AB печатается и, наконец, B

Answer 7

в Java у нас есть стек, в котором все наши вызовы хранятся со значениями

, при первом вызове ваша программа будет хранить ссылку на стек при первом вызове со значением 2, поэтому мы можем сказать

public static void testMethod(2){

      if(2 > 0){
Label A: testMethod(1); ==> this will trigger a call and our stack will refer to this line to coninue when the method ends
         System.out.print("A");
         testMethod(1);
         System.out.print("B");
      }
}

наша метка A будет выглядеть следующим образом, и вы должны знать, что у нас до сих пор нет печати

public static void testMethod(1){

      if(1 > 0){
Label B: testMethod(0); ==> in this case we have a new method call, new stack reference and we wait for this method return so we continue to next line
         System.out.print("A");
         testMethod(0);
         System.out.print("B");
      }
}

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

testMethod (2) ожидание в метке A ==> вызов TestMethod (1) ожидание в метке B вызов testMehod (0)

вы знаете, что 0 не больше 0, поэтому вы прекратите работу без обработки

это освободит метку B для перехода на следующую строку, где она напечатает A, затем вызов с нулевым значением, который ничего не будет делать, а затем напечатает B

вот наш первый AB

теперь он вернется к метке A и перейдет к следующей строке и напечатает A

у нас есть ABA, мы вспомним другой раз, когда testMethod1 мы знаем, что эта дорога напечатала AB, поэтому у нас будет

ABA + AB = ABAAB, затем вызов завершается изакончите, напечатав B и выйдите из вызова testMethod (2)

с печатью ABAABB