Как работает метод рекурсии?

Question

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

public class MysteryClass { 
    public static void mystery(int n) { 
     if (n > 0) { 
      mystery(n-1); 
      System.out.println(n * 4); 
      mystery(n-1); 
     } 
    } 
    public static void main(String[] args) { 
     MysteryClass.mystery(2); 
    } 
} 

выход

4 
8 
4 

То, что я понимаю, что

1. 2 больше, чем 0
2. 2 - 1 = 1
3. 1 больше, чем 0
4. 1 - 1 = 0
5. 0 не больше чем 0
6. Теперь мы переходим к этой линии: System.out.println(n * 4);
7. 1 * 4 = 4
8. 2 * 4 = 8
9. Вот я не понимаю, почему я получаю еще один «4 "на выходе

Что происходит на шаге 9?

Я использовал отладчик, но все еще не понимаю.

Answer 1

MysteryClass.mystery(2); 
    if (2 > 0) (true) ---> mystery(2-1); 
    | if(1 > 0) (true) ---> mystery (1-1); // Action (A) 
    | | if(0 > 0) (false) ---> // do nothing 
    | |  
    | System.out.println(1 * 4); 
    | mystery(1-1); 
    | 
    System.out.println(2 * 4); 
    mystery(2-1); ---> // repeat action (A) 

Answer 2

Если заменить п с 2, вы увидите exacly:

if (2 > 0) { 
    mystery(2-1); // prints 4 
    System.out.println(2 * 4); 
    mystery(2-1); // prints 4 
} 

У вас есть два вызова с mystery(2-1); One до и один после System.out.println

Поскольку все mystery(2-1); приведет печатать 4 , поэтому в результате 4 8 4

Answer 3

Если запустить этот код с n=2

mystery(n-1); 
    System.out.println(n * 4); 
    mystery(n-1); 

Это означает, что он пробегает полностью тайну (1) дважды. Сначала он запускает тайну (1), которая получает выход 4, но следующие две рекурсии с тайной (0) заканчиваются вены. Поэтому он продолжает

System.out.println(n * 4); 

Который является 8

Затем она проходит тайна (1) еще раз, который печатает 4.

Answer 4

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

Поскольку n не может быть изменен. Таким образом, вы будете запускать его еще раз с mystery(2-1);

Answer 5

Вы делаете двойную рекурсию - та же функция называется TWICE. Таким образом, ваш путь выполнения неверен.Обратите внимание на следующее изменение для ясности:

mystery(n-1); // pretend this is function "A" 
    System.out.println(n * 4); 
    mystery(n-1); // pretend this is function "B" 

1. тайну (2) // начать рекурсию
2. A (2-1) -> A (1) // п> 0, так что называть А ()
3. А (1-1) -> A (0) // п == 0, так что ничего не происходит
4. возвращения из (3)
5. Println (1 * 4) -> 4
6. возвращение от (2)
7. печатьln (n * 4) -> println (2 * 4) -> 8
8. B (2-1) -> B (1) // мы вернулись к первоначальному (1) вызову тайны
9. A (1- 0) -> A (0) // и т.д. ...

Answer 6

чтобы понять заменить тайну (п-1), чтобы закодировать в тайне:

int n1 = 2 
if (n1 > 0){ // step 1 
    int n2 = n1 - 1; // step2: 1 
    if (n2 > 0){ // step 3 
     int n3 = n2 - 1; // step4: 0 
     if (n3 > 0){ // step 5: false 
     ... 
     } 
     System.out.println(n2 * 4); // step 6: print 4 
     int n3_1 = n2 - 1; // step 7: 0 
     if (n3_1 > 0){ // false 
     ... 
     } 
    } 

    System.out.println(n1 * 4); // step 8: print 8 

    if (n2 > 0){ 
     int n3 = n2 - 1; // 0 
     if (n3 > 0){ // false 
     ... 
     } 
     System.out.println(n2 * 4); // step 9: print 4 
     int n3_1 = n2 - 1; // 0 
     if (n3_1 > 0){ // false 
     ... 
     } 
    } 

} 
} 

Answer 7

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

Вы можете заменить mystery(2) с тремя линиями

mystery(1); 
System.out.println(8); 
mystery(1); 

Поэтому ваш метод main может также сказать

public static void main(String[] args) { 
    mystery(1); 
    System.out.println(8); 
    mystery(1); 
} 

Вы можете заменить как тех mystery(1); звонков по

mystery(0); 
System.out.println(4); 
mystery(0); 

Это означает, что метод main может также сказать

public static void main(String[] args) { 
    mystery(0); 
    System.out.println(4); 
    mystery(0); 
    System.out.println(8); 
    mystery(0); 
    System.out.println(4); 
    mystery(0); 
} 

mystery(0); эффективно ничего не делает, так main может также сказать

public static void main(String[] args) { 
    System.out.println(4); 
    System.out.println(8); 
    System.out.println(4); 
}