Рекурсия - mystery1

Question

С трудом справившись с приведенным ниже кодом, я правильно ответил на первый звонок, так как условие сразу правильное.Тем не менее, второй вызов 4 вызывает у меня большое замешательство, я пришел к ответу 2, 1, однако он неверен - я явно все перепутал.Может ли кто-нибудь объяснить мне, почему мой ответ неверен и правильная разбивка процесса рекурсивной трассировки в этом примере.Я понимаю элементы рекурсии, но у меня возникают проблемы с отслеживанием.

public void mystery1(int n) {
    if (n <= 1) {
        System.out.print(n);
    } else {
        mystery1(n / 2);
        System.out.print(", " + n);
    }
}

mystery1(1);
mystery1(4);
mystery1(16);

Answer 1

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

Позвольте мне объяснить вам, как я выучил это, когда готовился к GATE (Graduate Aptitude Test in Engineering).

Думайте о каждом вызове функции как 2 части:

1. Печать
2. Вызов с делением пополам

Теперь все операции будут наложены на более старую до тех пор, пока у нас не выйдет рекурсия, и в функциональном цикле останется только Печать .Мы распечатаем в формате стека т.е. FIFO

Пример, если у нас есть эти элементы в стопке:

Верх: 4 ​​3 7 2 Bottom

Будет напечатано 4 3 7 2.

Теперь ответим на ваш вопрос:

Разбиваем ваши условные выражения на две половины, 1st будет если условие с Print 2nd будет else с его печатью .

Note : будет напечатана только одна часть, т. Е. 1st1 и это тоже без запятых (,).

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

Теперь объединяя mystery1 (1), mystery1 (4), mystery1 (16), окончательный результат будет: 1 1, 2, 4 1, 2, 4, 8, 16

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

Answer 2

В вашем методе:

public static void mystery1(int n) {
    if (n <= 1) {
        System.out.print(n);
    } else {
        mystery1(n / 2);
        System.out.print(", " + n);
    }
}

попробуйте заменить позицию System.out.print(", " + n); до mystery1(n / 2); вызова.

В первом случае, когда System.out после mystery1Вызовите, вы получите результат как 1, 2, 4, потому что сначала вы должны получить результат, а затем распечатать его.

Во втором случае, когда System.out до вызова mystery1, вы получите результат как , 4, 21, потому что сначала вы печатаете результат, а затем вычисляете следующий результат в функции.

Answer 3

Когда вы вызываете mystery1 (4), он переходит к другой части и вызывает mystery1 (2), так как n> 1.Оператор print будет выполнен только после того, как mystery1 (2) завершит выполнение.

То же самое происходит с mystery1 (2) и вызывает mystery1 (1).Он ожидает, что mystery (1) завершит выполнение.

Когда вызывается mystery1 (1), он печатает «1».

Затем mystery1 (2) продолжит работу и напечатает «, 2".

Наконец, mystery1 (4) продолжит и напечатает", 4 ".

Таким образом, ваш вывод будет 1,2,4