Comments 15
Чтобы не увидеть «StackOverflowError» на экране, нужно помнить о двух штуках: базисе и шаге рекурсии.
Это, определенно, не достаточное условие. На этом и стоит заострить внимание.
в случае с нахождением факториал мы использовали хвостовую рекурсию
Нет. Последнее действие там - умножение.
А вообще, обе задачи в статье, это пример когда лучше и проще решить обычным циклом. Вот всякие "древесно-развесистые" случаи с многократным рекурсивным вызовом, или взаимной рекурсией функций - другое дело. Конечно, они всегда могут быть переписаны на цикл/стек, или на хвостовую рекурсию, но код будет убойный.
Да, спасибо. В обоих случаях, действительно, используется головная рекурсия, поправила
Насчет использования цикла: в случае с факториалом, согласна, но здесь пример просто для базового понимания работы рекурсии приведен.
А вот в случае решения задачи с ListNode - мне кажется, код без рекурсии, будет довольно громоздким и сложным.
А вот в случае решения задачи с 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;
}
на мой взгляд, рекурсия гораздо понятнее, если в ней разобраться
Но тут, кому что нравится)
кому что нравится)
Проблема в том, что на достаточно длинных списках это свалится в переполнение стека. А тогда уж не до эстетики.
Для Java не важен тип рекурсии. В языках с оптимизацией хвостовой рекурсии это важно.
Пример кода для подсчёта факториала не правильный. Факториал нуля равен единице.
Хвостовая рекурсия показана неправильно. Рекурсивный вызов должен быть единственным и являться последним действием в функции перед возвратом из неё.
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);
}
Про непрямую и косвенную рекурсию не было плана рассказывать в этой статье:)
По поводу головной и хвостовой - обсуждали в комментарии выше: оба примера, действительно являются головной рекурсией, в статье скорректировала.
Рекурсивный вызов должен быть единственным
Единственным в пределах исполняемой ветки, имеете в виду?
Рекурсия в Java с примером решения задачи с LeetCode