Зачем нужна рекурсия в реальных случаях?

Question

[pinkhead_psd]

Недавно изучил (!= понял) тему с рекурсией. Понял, что можно очень мудрено возвести число в нужную степень или посчитать кол-во символов в числе, для такой задачи как по мне достаточно обычного цикла, поправьте если нет и почему. Так вот, вопрос заключается в том, что в каких реальных проектах или задачах может потребоваться этот демон, я бы сказал даже в чем его реальная суть, потому что я видимо не до конца её понял. Пока что мой мозг видит рекурсию как обычный цикл, только задом наперед.

Comments

[GavriKos]

Надо пометить вопрос как дубликат, и в качестве ссылки на дубликат дать этот вопрос

[Василий]

Чел, будет много фигни, которая "лол, зачем это нужно?"
А через 2 месяца столкнёшься с задачей, и вспомнишь что когда-то тыкал что-то, что поможет, и как миленький побежишь повторять материал.
Не стоит по каждому функционалу плодить такие вопросы. Просто прими это, и живи дальше.
Кстати, цикл for не нужен, while достаточно для любой ситуации.
Умножение тоже не нужно, можно зациклить сложение.
Этот список можно продолжать до тех пор, пока в итоге не останется ассемблер.

Запомни - ВСЁ что ты видишь, нужно для облегчения жизни программиста. Иначе бы ты писал на ассемблере.
Кстати, чуть не забыл, циклы тоже не нужны. Go to достаточно для любой задачи.

Answer 1

[mayton2019]

Рекурсия нужна при обработке иерархических данных. Например - обойти файлы и каталоги
в файловой системе и выполнить какое-то действие. Или действие с условием. Например если
в текущем фолдере есть фолдер .git - то выполнить какой-то git script.

Рекурсия может понадобиться при работе с документами XML/JSon (шаблон composer). И хотя
в некоторых API рекурсия может быть частично скрыта за языками XPath/JSonPath тем не меннее
ее рекурсивная природа остается налицо. Кроме того если вам достался узкий API типа DomDocument
без поисковых диалектов - то обойти его можно на любом ЯП с рекурсивной функцией.

Рекурсия нужна при парсинге сайтов. Это вобщем просто более расширенная трактовка работы с файловой
системой. Если Url-s это как-бы файлы в web пространстве и они имеют ссылки друг на друга - то вы
можете рекурсией это все обходить.

Рекурсия почти всегда нужна при работе с графами. Берите любой алгорим на теорию графов и я готов
спорить что 99% он будет содержать рекурсию.

Все настольные игры (шахматы-шашки) в основе своего алгоритма альфа-бета поиска с отсечениями и
BWF базируются на рекурсии.

Comments

[wisgest]

Всё это делается и без рекурсии (но со стеком, разумеется).

[mayton2019]

wisgest, я не против. Обучите автора работе со стеком. Только перед этим нужно хотя-бы дать обзор существующим методам чтоб было что с чем сравнивать.

[GavriKos]

wisgest, внезапно рекурсия работает на стеке, да )))

[pinkhead_psd]

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

[pinkhead_psd]

Но по сути, все также это дело можно заменить циклом с условием. Может знаете хорошие примеры или ссылки на них?

[wisgest]

GavriKos, неявно, да. То же самое можно сделать явно без рекурсии. При этом стек не будет засорятся запоминанием адреса возврата.

[mayton2019]

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

Есть техники описания т.н. генераторов последовательностей. Например список чисел Фибоначчи. Эти генераторы тоже имеют вид рекурсивных функций. Но при этом стек им не нужен. Они - ближе к итераторам по своей природе.

[mayton2019]

pinkhead_psd, еще рекурсия очень важна при описании различного рода грамматик. Такие технологии как BNF/EBNF, yacc, bizon, antlr e.t.c. - это все описательные языки которые объявляют какой-то синтаксис. Например синтаксис S-expressions или JSON может быть описан десятком строк описания грамматики на EBNF.

Есть описательные рекурсивные техники для рекурсивных структур данных. Например узел бинарного дерева описывается как Нода у которой есть две ссылки на такие-же Ноды. Это поддерживается даже в языке С.

[pinkhead_psd]

mayton2019, картинка такая, что это более лаконичный подход для работы, как вы сказали с иерархической структурой. С помощью рекурсии построить или обработать тоже самое B-tree будет проще, но быстрее? Я так понимаю рекурсия более ресурсоёмкий процесс, потому что как минимум мы загружаем стек вызовов миллионом функций или я неправильно понял?

[mayton2019]

pinkhead_psd, не думайте сейчас о накладных расходах. Просто попробуйте написать рекурсивный обход Б-дерева. И если он будет успешным (без ошибок) и без stack overflow - то тогда попробуйте декомпозировать в решение на базе цикла.

Но мой опыт подказывает что 80% разработки на этом завершаются. Всегда технически проще подрегулировать размер стека (для Java там есть отдельный параметр) чем платить программисту сотни и тысячи зелени за размотку рекурсии в цикл со структурой типа Deque.

В наше время - самый дорогой ресурс - это вовлеченность специалиста в задачу. Вот честно. Все стало дешево. Диски. Память. Вычислительные ноды. Как грязи всего много. А людей не хватает. И денег на оплату синьоров не хватает.

Answer 2

[Griboks]

Вы правы, рекурсию всегда можно заменить циклом. Более того, рекурсия - это и есть цикл, который за вас выполняет движок языка. Главный вопрос - что для вас будет удобнее: рекурсия или цикл.

Зачем нужна рекурсия в реальных случаях?

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

Answer 3

[Vfreelance]

пример: меню на сайте 5 уровней вложенности. отрисовывваем первый уровень, если пункт содержит подпункты - для него вызываем этот же код и так далее

Answer 4

[Владимир Коротенко]

Реальный проект парсинг любого магазина по вложенным категориям.
Вы допустим предположите что разумная глубина 6 уровней, а этот маньяк что уровней должно быть 14

Answer 5

[mletov]

Наверное, файлы и папки, упомянутые выше - это наиболее универсальный пример, без привязки к предметной области, языку программирования или типу приложения (веб, мобайл, десктоп).

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

Answer 6

[VoidVolker]

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

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

Неправильно видит. "Зад" и "перед" не имеют к этому отношения. Цикл - это строгий вызов подпрограммы/куска кода со счетчиком и условием либо просто с условием и без необходимости объявлять отдельную функцию. Цикл работает пока соблюдается условие и изнутри цикла код влияет только на условие, в большинстве ЯП есть выход из цикла. В рекурсии же нету ни условий ни счетчиков - это все остается на выбор программиста. Это более низкий уровень в сравнении с циклом. Если цикл это строгое решение под определенные задачи, то рекурсия - это более гибкое и универсальное решение. И то и то нужно и используется в различных ситуациях.

Comments

[pinkhead_psd]

Я вас понял, концепция понимания и видения может быть у всех разной. Вы описали это более программно
P.S: если в рекурсии нет базового условия, то она же будет бесконечной?

[VoidVolker]

Да, будет бесконечной. Выход из рекурсии - это выход из функции до её повторного вызова.

function foo() {
    // ... Полезная работа ...
    foo()
}

Пример реализации простейшего цикла со счетчиком через рекурсию:

function loop(cnt, rule, action) {
    if (rule(cnt)) {
        action(cnt)
        loop(cnt+1, rule, action) 
    }    
}

loop(0, i => i < 3, console.log)
0
1
2

[VoidVolker]

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

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

[shurshur]

pinkhead_psd,

P.S: если в рекурсии нет базового условия, то она же будет бесконечной?

В ленивых вычислениях может быть и бесконечной.

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

Answer 7

[CityCat4]

Вот типичная задачка.

В каталоге с файлами и другими подкаталогами нужно исправить права доступа на файлы и не трогать подкаталоги. В подкаталогах могут быть еще подкаталоги и файлы (глубина ограничена только возможностями ФС). Нужно обойти все уровни вложенности и исправить права на все файлы.