Рекурсия в Java с примером решения задачи с LeetCode

[ris58h]

Чтобы не увидеть «StackOverflowError» на экране, нужно помнить о двух штуках: базисе и шаге рекурсии.

Это, определенно, не достаточное условие. На этом и стоит заострить внимание.

[Alexandroppolus]

в случае с нахождением факториал мы использовали хвостовую рекурсию

Нет. Последнее действие там - умножение.

А вообще, обе задачи в статье, это пример когда лучше и проще решить обычным циклом. Вот всякие "древесно-развесистые" случаи с многократным рекурсивным вызовом, или взаимной рекурсией функций - другое дело. Конечно, они всегда могут быть переписаны на цикл/стек, или на хвостовую рекурсию, но код будет убойный.

[akozyrenko]

Да, спасибо. В обоих случаях, действительно, используется головная рекурсия, поправила

Насчет использования цикла: в случае с факториалом, согласна, но здесь пример просто для базового понимания работы рекурсии приведен.

А вот в случае решения задачи с ListNode - мне кажется, код без рекурсии, будет довольно громоздким и сложным.

[Rsa97]

А вот в случае решения задачи с ListNode - мне кажется, код без рекурсии, будет довольно громоздким и сложным.

Без рекурсии код будет несколько больше по размеру, но гораздо понятнее:

public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    }

    if (list2 == null) {
        return list1;
    }

    ListNode result;
    if (list1.getVal() < list2.getVal()) {
        result = list1;
        list1 = list1.getNext();
    } else {
        result = list2;
        list2 = list2.getNext();
    }

    ListNode current = result;
    while (list1 != null && list2 != null) {
        if (list1.getVal() < list2.getVal()) {
            current.setNext(list1);
            current = list1;
            list1 = list1.getNext();
        } else {
            current.setNext(list2);
            current = list2;
            list2 = list2.getNext();
        }
    }

    if (list1 != null) {
        current.setNext(list1);
    } else {
        current.setNext(list2);
    }

    return result;
}

[akozyrenko]

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

Но тут, кому что нравится)

[Alexandroppolus]

кому что нравится)

Проблема в том, что на достаточно длинных списках это свалится в переполнение стека. А тогда уж не до эстетики.

[Andrey_Solomatin]

А не отвалится по памяти? В Питоне искусственно ограничили глубину стека, чтобы не скушать всю память. На C# недавно дебажил бесконечную рекурсию, сервер тихонечко съедал всю память.

[Alexandroppolus]

Видимо, везде по разному. В js переполняется стек, как в других - не знаю..

[Andrey_Solomatin]

Для Java не важен тип рекурсии. В языках с оптимизацией хвостовой рекурсии это важно.

[tmk826]

Пример кода для подсчёта факториала не правильный. Факториал нуля равен единице.

[akozyrenko]

Да, спасибо, действительно ошибка, поправила

[Rsa97]

Хвостовая рекурсия показана неправильно. Рекурсивный вызов должен быть единственным и являться последним действием в функции перед возвратом из неё.

public int calculateFactorial(int x, int acc) {
    if (x == 0) {
        return acc;
    }
    return calculateFactorial(x - 1, acc * x);
}

public int factorial(int x) {
    return calculateFactorial(x, 1);
}

При головной рекурсии вызов также должен быть единственным и являться первым действием в одной из основных веток функции.

public int factorial(int x) {
    if (x > 0) {
        int t = factorial(x - 1);
        return t * x;
    }
    return 1;
}

И ничего не сказано о взаимной (непрямой, косвенной) рекурсии, когда несколько функций вызывают друг друга.

public int is_even(int x) {
    if (x == 0) {
        return true;
    }
    return !is_odd(x - 1);
}

public int is_odd(int x) {
    if (x == 0) {
        return true;
    }
    return !is_even(x - 1);
}

[akozyrenko]

Про непрямую и косвенную рекурсию не было плана рассказывать в этой статье:)

По поводу головной и хвостовой - обсуждали в комментарии выше: оба примера, действительно являются головной рекурсией, в статье скорректировала.

[ris58h]

Рекурсивный вызов должен быть единственным

Единственным в пределах исполняемой ветки, имеете в виду?

[Rsa97]

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