Как работает рекурсия в JAVA?

Question

Есть небольшой код

public class Driver {
    public static void main(String[] args) {
        System.out.println(drive(4, 6));
    }
    public static int drive(int a, int b) {

        if (a == 0) return Math.abs(a - b);

        return Math.min(
                        drive(a - 1, b + 1),
                        drive(a - 1, b + 1)
        );
    }
}

Вопрос: почему когда "a" становится 0, не происходит выход из метода, а наоборот "a" становится 1, потом 2, потом снова 1 и так ещё несколько итераций.

Целый вечер сижу никак не могу разобраться как это работает. В дебаг режиме запускал код, и всё равно не понял откуда берутся значения "a" после того, как она опускается к 0.

Спасибо!

Answer 1

Eсли немного поменять код то можно увидеть сколько раз будет вызывается рекурсия

public class Driver {
    public static void main(String[] args) {
        System.out.println(drive(4, 6));
    }
    public static int drive(int a, int b) {
        System.out.printf("\n(a = %d b = %d)", a, b);
        if (a == 0) return Math.abs(a - b);

        return Math.min(
                        drive(a - 1, b + 1),
                        drive(a - 1, b + 1)
        );
    }
}

вывод такой

(a = 4 b = 6)
(a = 3 b = 7)
(a = 2 b = 8)
(a = 1 b = 9)
(a = 0 b = 10)
(a = 0 b = 10)
(a = 1 b = 9)
(a = 0 b = 10)
(a = 0 b = 10)
(a = 2 b = 8)
(a = 1 b = 9)
(a = 0 b = 10)
(a = 0 b = 10)
(a = 1 b = 9)
(a = 0 b = 10)
(a = 0 b = 10)
(a = 3 b = 7)
(a = 2 b = 8)
(a = 1 b = 9)
(a = 0 b = 10)
(a = 0 b = 10)
(a = 1 b = 9)
(a = 0 b = 10)
(a = 0 b = 10)
(a = 2 b = 8)
(a = 1 b = 9)
(a = 0 b = 10)
(a = 0 b = 10)
(a = 1 b = 9)
(a = 0 b = 10)
(a = 0 b = 10)10

Answer 2

Вас путает то что в функции drive два рекурсивных вызова. Я нарисую дерево вызовов, а вы проверите в отладчике, что значения a и b меняются именно в таком порядке:

drive(4, 6)
    drive(3, 7)
        drive(2, 8)
            drive(1, 9)
                drive(0, 10)
                drive(0, 10)
            drive(1, 9)
                drive(0, 10)
                drive(0, 10)
        drive(2, 8)
            drive(1, 9)
                drive(0, 10)
                drive(0, 10)
            drive(1, 9)
                drive(0, 10)
                drive(0, 10)
    drive(3, 7)
        drive(2, 8)
            drive(1, 9)
                drive(0, 10)
                drive(0, 10)
            drive(1, 9)
                drive(0, 10)
                drive(0, 10)
        drive(2, 8)
            drive(1, 9)
                drive(0, 10)
                drive(0, 10)
            drive(1, 9)
                drive(0, 10)
                drive(0, 10)

Если вы в отладчике поставить точку останова в начале функции, то получите такую последовательность значений a:

4 3 2 1 0 0 1 0 0 2 1 0 0 1 0 0 3 2 1 0 0 1 0 0 2 1 0 0 1 0 0

Посмотрите стек вызовов. В нём значения a будут выглядеть так:

БЛОГ НА HUSL

Как работает рекурсия в JAVA?

Ответы (2 шт):