Рекурсия, зачем она нужна, и используете ли вы её?

Question

[K-VKO]

При изучении одного из языков программирования задался таким вопросом: а зачем нужна рекурсия, если всегда можно обойтись без неё?

Неужели если я научусь ей пользоваться и приду в хорошую контору, то там все (особенно джуны) будут понимать мой код? - Это главный вопрос

Comments

[Lynn «Кофеман»]

Формально любой алгоритм с рекурсией можно написать без неё на циклах. Но станет ли он от этого понятнее это большой вопрос. Я сильно сомневаюсь.

[pfg21]

рекурсия это инструмент.
со своими плюсами и минусами, областями эффективного и не эффективного применения и т.д.
как и все остальные инструменты.
насколь ты им умеешь пользоваться инструментами/разными инструментами настолько ты и специалист.

Answer 1

[Илья]

Самый простой пример: построение дерева элементов с неопределённым уровнем вложенности.

Неужели если я научусь ей пользоваться и приду в хорошую контору там все (особенно джуны) будут понимать мой код?

Умение пользоваться рекурсией не залог того, что твой код хороший и понятный.

Answer 2

[Василий Банников]

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

Некоторые алгоритмы очень хорошо выглядят, если реализуются через рекурсию (но не всегда эффективно).
Те же алгоритмы, которые строятся на стратегии "разделяй и властвуй", когда у тебя есть большой набор данных, и ты можешь его разделить на наборы по меньше, которые обрабатывать независимо.
Например вот псевдокод для конвертации json-DOM в объекты:

fun ConvertJsonElementToObject(element: JsonElement): Object {
  return match(element.type) {
    Number(num) -> num as Object,
    String(str) -> str as Object,
    Array(elements) -> elements.map(ConvertJsonElementToObject) as Object,
    Object(dict) -> dict.mapValues(ConvertJsonElementToObject) as Object,
    Null -> null as Object
  }
}

Answer 3

[Alexandroppolus]

Если внутри функции делается несколько рекурсивных вызовов, то вариант цикл+стек будет смотреться сложно и вышеупомянутые джуны ощутят трудности его понимания. Или, например, кейс, когда есть взаимная рекурсия двух или более функций - там придется код как-то перекроить, смотря по ситуации.

Нерекурсивный вариант обязательно следует использовать, когда можно обойтись без стека, как в избитом примере вычисления факториала. Так же - когда существует ненулевая вероятность, что будет переполнение стека: например, функция работает с произвольным двоичным деревом, и может получить на вход очень сильно несбалансированное дерево большой высоты. Ещё есть разные специальные кейсы. Допустим, обход графа в глубину: если сделать его нерекурсивным, то можно будет легко заменить в функции стек на очередь и получить обход в ширину, или даже на приоритетную очередь, тогда будет "поиск по критерию стоимости"

Answer 4

[Александр Скуснов]

При функциональном программировании (Haskell) нет циклов, только рекурсия.

Answer 5

[calculator212]

Неужели если я научусь ей пользоваться и приду в хорошую контору, то там все (особенно джуны) будут понимать мой код? - Это главный вопрос

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