Рекурсия

В книге "Грокаем алгоритмы" в главе 3, началось изучение Рекурсии. В подглаве "Стек вызовов с рекурсией" делается пример метода вычисления факториала с применением рекурсии

public static int fact(int x) {
        if (x == 1) //базовый случай рекурсии ( т.е. остановка)
            return 1;
        else
            return x * fact(x - 1);
    }

Тут вроде всё понятно, так как дальше идёт иллюстрация того, что происходит в стэке. Далее наткнулся на статью https://habr.com/ru/post/275813/ где идёт решение задач с помощью рекурсии. И застопорился, сразу же на первой))) "Дано натуральное число n. Выведите все числа от 1 до n." Подсмотрел в этой же статье решение:

public static String taskA (int x) {
        // Базовый случай
        if (x == 1) {
            return "1";
        }
        // Шаг рекурсии / рекурсивное условие
        return taskA(x - 1) + " " + x;
    }

Тут у меня n = 3 И никак не могу понять одну вещь: то есть получился стэк из трёх методов вызова(всё как в иллюстрации "Грокаем Алгоритмы") при x = 1, возвращает строку с значением "1". Но, что происходит дальше? и почему на экран выводятся все числа от 1 до 3 (ну в случае с 1, всё понятно) Ведь получается, что блок стэка, где x = 1, выбрасывается и следующий идёт x = 2, то как же тогда получается цифра 2?, если return taskA(2 - 1) + " " + 2? Спасибо!

Комментарии (5)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Badger

Уровень 22

Expert

18 июня 2020, 17:02

Попробую показать иллюстрацией :)

Максим

Уровень 23

18 июня 2020, 18:28

Спасибо за иллюстрацию

hidden #598481

Уровень 27

18 июня 2020, 15:01

решение

Самый внутренний метод (C) вернул строку "1" в тот метод, в котором он был вызван (B). В методе B ты находишься в строке return "1" + " " + x, где "1" - это строка, возвращенная из метода C в метод B, а x = 2. Получается, что Y возвращает строку "1 2" в метод, который вызвал метод B, т.е. в метод A, на уровень выше. В методе A выполняется команда return "1 2" + " " + x, где "1 2" - это строка, возвращенная из метода B в метод A, а x = 3. Поэтому метод А (внешний) возвращает строку "1 2 3" A,B,C - это условные названия методов в стеке, где метод А(x=3) вызывает метод B(x=2), а метод B вызывает метод С(x=1)

18 июня 2020, 18:29

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

18 июня 2020, 19:00

Я назвал методы по порядку их вызова. Допустим, метод main вызывает метод taskA, тот вызывает сам себя еще несколько раз. Стек вызовов будет таким: main -> taskA -> taskA -> taskA -> ... -> taskA Вот я их слева направо условно и назвал в алфавитном порядке. Самый последний вызванный метод, конечный, который никого не вызовет, завершит свою работу самым первым, и вернет результат в предыдущий, предпоследний метод, выполнив команду return "1". В случае с тремя аргументами это будет метод (условно) C, вернувший результат в метод B:

То есть "С" - это метод, который был вызван последним, соответственно свою работу он закончит первым. В этом и заключается концепция стека. "Внешним" методом я называю тот, который содержит в себе вызов другого метода. Не знаю, насколько это корректно, мне казалось логичным.