Что происходит, когда рекурсия вызывается дважды в методе?

Question

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

Рекурсивный метод вызывается с аргументами "ABCD" и 2, то есть recMethod("ABCD", 2);.

public void recMethod(String str, int n) { 
    if(n >= 0) { 
    recMethod(str, n – 1); 
    System.out.print(str.charAt(n)); 
    recMethod(str, n – 1); 
    } 
} 

Есть ли кто-нибудь, кто может объяснить, что происходит? Первый рекурсивный вызов меня действительно смущает.

Answer 1

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

Пожалуйста, попробуйте сделать то же самое, и не стесняйтесь задавать больше вопросов, я надеюсь, что это поможет!

Answer 2

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

public void someMethod() { 
    someOtherMethod(); 
    someLastMethod(); 
} 

Глядя на моем примере это очевидно, что someLastMethod будет называться после того, как someOtherMethod закончил. Это действительно неважно, замените ли вы someOtherMethod чем-то рекурсивным. Его нужно закончить до того, как можно будет назвать someLastMethod. Когда снова глядя на ваш рекурсивный метод:

public void recMethod(String str, int n) { 
    if(n >= 0) { 
     recMethod(str, n – 1); 
     System.out.print(str.charAt(n)); 
     recMethod(str, n – 1); 
    } else { // base case added for clarity 
     return; 
    } 
} 

Для каждого вызова, где n >= 0, до того, как метод System.out.print называется вызов recMethod должен быть вызван. Каждый вызов recMethod имеет свои собственные n и str, поэтому их можно считать разными способами, за исключением того, что их код «очень похож».

Каждый вызов будет либо соответствовать базовому регистру, либо нужен результат того же метода с n декрементированным, поэтому я хотел бы начать с базового футляра и работать сам назад, то есть когда n равно -1. Представьте, что вы звоните recMethod("ABCD",-1), что произойдет? Ну, он ничего не печатает или «».

Затем я смотрю на recMethod("ABCD",0), и он вызывает базовый регистр, который, как мы знаем, ничего не делает, затем печатает «A», а затем он вызывает то же, что и первое утверждение, которое снова ничего не делает. Таким образом, он печатает «А»

Если мы посмотрим на recMethod("ABCD",1). Мы знаем, что он вызывает recMethod("ABCD",0), который печатает «A», затем печатает «B», затем вызывает recMethod("ABCD",0), который печатает «A». Таким образом, он печатает «ABA»

Если мы посмотрим на recMethod("ABCD",2). Мы знаем, что он вызывает recMethod("ABCD",1), который печатает «ABA», затем печатает «C», затем вызывает recMethod("ABCD",1), который печатает «ABA». Таким образом, он печатает «ABACABA»

Если мы посмотрим на recMethod("ABCD",3). Мы знаем, что он вызывает recMethod("ABCD",2), который печатает «ABACABA», затем печатает «D», затем вызывает recMethod("ABCD",2), который печатает «ABACABA». Таким образом, он печатает «ABACABADABACABA»

С "abcd".charAt(4) не будет работать, не имеет смысла продолжать.Возможно, код должен пройти тест на это или, возможно, он должен быть закрытым и иметь общедоступный без n, который гарантирует, что n никогда не выходит за рамки str границ?

Если вы хотите сделать метод, который работает рекурсивно, вы делаете то же самое.

1. Что должно случиться для базового корпуса. (Как он должен остановиться)

2. Что должно произойти, если это не основной случай, выраженный так, как если бы метод работал так, как предполагалось. Ловушка здесь заключается в том, что вам нужно убедиться, что каждый вызов того же метода здесь представляет собой немного более простую проблему, в которой рекурсия должна попасть в базовый регистр, иначе вы получите бесконечную рекурсию!

Thats it! Это будет работать.