Как работает рекурсивный метод?

Question

[meinhard]

Объясните пожалуйста подробно по шагам, что происходит на каждом шаге этого кода

Два часа уже бьюсь, никак не могу понять принципа, понятно только, что происходит до значения = 1, а куда оно return'ится и что дальше происходит - "темный лес".

class Factorial {

    int fact(int n) {
        int result;
        if (n == 1) {
            return 1;
        }
        result = fact(n - 1) * n;
        return result;
    }
}
class Recursion {

    public static void main(String args[]) {
        Factorial f = new Factorial();

        System.out.println("Факториал 3 равен " + f.fact(3));
    }
}

Answer 1

[veontomo]

Значение возвращается тому, кто его запросил.
Например, если запросить f.fact(1), то метод Factorial::fact сразу вернет 1.
Для запроса f.fact(2) цепочка вызовов будет такой:
сначала запрос Factorial::fact(2), который вернет Factorial::fact(1) * 2.
В ответе есть снова запрос Factorial::fact(1), который возвращает 1. Таким образом, получаем 2*1, т.е. 2.

По этой же схеме проходят и остальные примеры:
f.fact(10) -> f.fact(9) * 10 -> f.fact(8) * 9 * 10 -> ... -> f.fact(1) * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10.

Comments

[meinhard]

Почему же тогда не возвращается - 1 или 2, а возвращается 6. Я просто не могу понять как пошагово работает данный блок c n=3:

int fact(int n) {
        int result;
        if (n == 1) {
            return 1;
        }
        result = fact(n - 1) * n;
        return result;
    }

[Volodymyr S.]

С n = 3 умножает 3 на fact(2), а fact(2) умножает 2 на fact(1), а fact(1) = 1. Получается fact(3) = 3 * fact(2) = 3 * (2 * fact(1)) = 3 * 2 * 1 = 6.

[meinhard]

вот начинается метод fact с параметром 3, пролетаем if(), попадаем на строку result = fact(3-1)*3 (вопрос, вот тут что-то вычисляется или нет?), в result кладется fact(2)*3, вызывается следующая грубо говоря "итерация" уже с параметром 2, result = fact(2-1)*2, result = fact(1)*2, затем попадем в if() с параметром 1, он нам возвращает 1 (вопрос куда он ее возвращает return 1, в result?) и вот что потом происходит, в какой момент в этом блоке происходит умножение 3*2*1 и возврат значения вызвавшему объекту?

[meinhard]

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

Answer 2

[sdevalex]

Сделай

// ...
result = fact(n - 1) * n;
System.out.println(result);
// ...

Станет понятно, что куда возвращается.

Comments

[meinhard]

Да делал я уже так, выведенные в консоли цифры - 2 и 6 еще больше меня запутали. Мне нужно "разжевать и в рот положить" =)

[swinntus]

ну так правильно она вначале высчитывает факториал от 1, который не принтится, потом от 2-ки(это и есть первое число), потом от 3-ки(2-е число).
По сути этот метод просто перебирает все числа от 1 до n и перемножает их начиная с меньшего.
При таком выводе и получится ряд типа: 2 6 24 120 720 и тд

Answer 3

[swinntus]

По сути, этот метод зациклан до того момента, пока n не будет = 1, после чего он начинает выполнять умножение вначале на 2, потом на 3 и т.д. пока значение не будет = n, после чего метод возвращает полученное произведение

Answer 4

[afiskon]

Метод вызывает сам себя. Что тут непонятного?