27 / 27 / 16
Регистрация: 22.08.2017
Сообщений: 126
1

Реальное применение рекурсивных вычислений

24.11.2017, 13:39. Показов 1521. Ответов 26
Метки нет (Все метки)

Добрый день.

Ползая по форуму https://www.cyberforum.ru я обратил внимание, что довольно часто студентам задают задачи на рекурсивные вычисления.

В связи с этим возникли вопросы:

1. Так ли уж часто в реальных проектах используются рекурсивные вычисления?

2. Так ли уж полезны рекурсивные вычисления? Какие преимущества имеют рекурсивные вычисления по сравнению с обычным циклом? Ведь все, что можно вычислить с помощью рекурсивных вычислений, можно вычислить с помощью обычного цикла. При этом решение с обычным циклом выгодно отличается от рекурсивных вычислений тем, что при обычном цикле стек не проваливается, грозя реальным падением приложения.

Спасибо.

PS. Извините, в названии темы ошибка. Имелось ввиду конечно же "Реальное применение рекурсивных вычислений". Не знаю как поправить название темы, похоже этого нельзя сделать на этом форуме. Хотел удалить тему и заново ее запостить с поправленным названием темы, но этого тоже нельзя сделать.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.11.2017, 13:39
Ответы с готовыми решениями:

Реальное применение локальных классов
В общем-то читал Александреску и вспомнил старую главу о локальных классах. Там приводился пример...

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

Применение рекурсивных мьютексов
Задался таким вопросом - является ли применение рекурсивных мьютексов признаком плохой архитектуры?...

Применение функций для вычислений в различных системах счисления
Разработать программу на языке С++ для решения следующей задачи. Заданы два числа — А и B, первое...

26
Падаван С++
447 / 261 / 89
Регистрация: 11.11.2014
Сообщений: 916
24.11.2017, 13:53 2
pepsicoca2, все зависит от проекта, в 90 процентах случаев вы с математикой вообще связаны не будете, а если и будете то скорее всего будет юзятся уже какой нибудь фреймворк, для студентов вычисления на рекурсии показывают чтобы наглядно показать что это, легче сделать сначала расчет какого нибудь интеграла, а уже потом показывать обход бинарного дерева к примеру

Добавлено через 2 минуты
pepsicoca2, а так конечно, рекурсия менее эфективна чем цикл, но в некоторых моментах намного удобнее реализовать рекурсивный алгоритм, к примеру обход конем шахматной доски,в разы легче как по мне рекурсией сделать, чем циклами
0
Эксперт С++
8711 / 4293 / 956
Регистрация: 15.11.2014
Сообщений: 9,733
24.11.2017, 14:25 3
Цитата Сообщение от pepsicoca2 Посмотреть сообщение
Так ли уж часто в реальных проектах используются рекурсивные вычисления?
не очень часто.

Цитата Сообщение от pepsicoca2 Посмотреть сообщение
Так ли уж полезны рекурсивные вычисления?
не очень полезны.

Цитата Сообщение от pepsicoca2 Посмотреть сообщение
Какие преимущества имеют рекурсивные вычисления по сравнению с обычным циклом?
простота реализации.
Цитата Сообщение от pepsicoca2 Посмотреть сообщение
При этом решение с обычным циклом выгодно отличается от рекурсивных вычислений тем, что при обычном цикле стек не проваливается, грозя реальным падением приложения.
совершенно верно.
потому рекурсию частенько заменяют на цикл + стек.


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

собственно, простота реализации - единственная киллер-фича рекурсивных алгоритмов.
во всех остальных аспектах они проигрывают циклам,
и не рукомендуются к использованию.
0
1463 / 1005 / 455
Регистрация: 30.10.2017
Сообщений: 2,793
24.11.2017, 14:26 4
pepsicoca2, если научитесь ее применять, и придет понимание в каких местах программы можно ее использовать, в некоторых моментах она может существенно облегчить жизнь.

Еще хороший классический пример по рекурсии - задача о Ханойской башне.
0
3811 / 3118 / 866
Регистрация: 25.03.2012
Сообщений: 11,521
Записей в блоге: 1
24.11.2017, 14:32 5
Цитата Сообщение от hoggy Посмотреть сообщение
не очень полезны.
Сильное заявление.
Если имелась в виду производительность и память на стеке, то да, Экономным лучше не пользовать.
Но это с точки зрения машины.
А с точки зрения человека, программирующего её, рекурсивный алгоритм будет куда нагляднее, чем скажем эмуляция этого же алгоритма на искусственном стеке. Я про случаи когда алгоритм реально рекурсивный по природе, а не искусственно усложнён типа "сложите все числа от 1 до N рекурсивной функцией".
0
зомбяк
1564 / 1213 / 345
Регистрация: 14.05.2017
Сообщений: 3,935
24.11.2017, 14:32 6
Цитата Сообщение от QuakerRUS Посмотреть сообщение
и придет понимание в каких местах программы можно ее использовать,
вот в соседней теме есть её пример - Создание n-мерного динамического массива - хотя это не собственно рекурсия функций, а рекурсивное построение шаблонных классов, когда класс n-мерного массива вмещает линейный массив (n-1)-мерных массивов.
0
Падаван С++
447 / 261 / 89
Регистрация: 11.11.2014
Сообщений: 916
24.11.2017, 14:36 7
Ну и тоже вот конкретный пример вычислений и на шаблонах, и просто рекурсией тык это в довесок примера TRam_,
0
Эксперт С++
8711 / 4293 / 956
Регистрация: 15.11.2014
Сообщений: 9,733
24.11.2017, 14:52 8
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
А с точки зрения человека, программирующего её, рекурсивный алгоритм будет куда нагляднее
Цитата Сообщение от hoggy Посмотреть сообщение
простота реализации - единственная киллер-фича рекурсивных алгоритмов.
...
0
3505 / 2127 / 395
Регистрация: 09.09.2017
Сообщений: 8,843
24.11.2017, 15:16 9
Цитата Сообщение от pepsicoca2 Посмотреть сообщение
Ведь все, что можно вычислить с помощью рекурсивных вычислений, можно вычислить с помощью обычного цикла.
Да ну? Покажите как обычным циклом обойти дерево, да еще с неизвестным заранее количеством ветвей. Или то что указал TRam_, создание многократно вложенного массива, причем степень вложенности опять-таки неизвестна.
Не все задачи можно разложить на цикл.
0
зомбяк
1564 / 1213 / 345
Регистрация: 14.05.2017
Сообщений: 3,935
24.11.2017, 15:24 10
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
Покажите как обычным циклом обойти дерево
reinterpret_cast-ом по указателю на следующий элемент. Таким способом можно добавлять/убавлять любое количество "звёздочек" .
0
27 / 27 / 16
Регистрация: 22.08.2017
Сообщений: 126
24.11.2017, 15:29  [ТС] 11
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
Покажите как обычным циклом обойти дерево, да еще с неизвестным заранее количеством ветвей.

А какие проблемы обойти дерево в цикле? Обходишь и все. В цикле. Совершенно так же, как и в рекурсии. Только при большом дереве у Вас стек упрется в ограничение ОС, а в цикле просто долго будет крутиться цикл, но хотя бы приложение не упадет.
0
Диссидент
Эксперт C
26970 / 16845 / 3705
Регистрация: 24.12.2010
Сообщений: 37,821
24.11.2017, 15:36 12
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
Не все задачи можно разложить на цикл.
Ерунда. Все. Можно.
Кнута "Искусство программирования" не почитывали? Он почему-то из каких-то соображений вообще рекурсию там избегает. И явно рекурсивные задачи решает, моделируя стек. Конечно, получается весьма громоздко. Но возможность есть.
0
3505 / 2127 / 395
Регистрация: 09.09.2017
Сообщений: 8,843
24.11.2017, 16:21 13
Все равно не представляю как, скажем, тот же вложенный массив создать без рекурсии или десятка одинаковых функций.
0
1463 / 1005 / 455
Регистрация: 30.10.2017
Сообщений: 2,793
24.11.2017, 16:42 14
COKPOWEHEU, цикл + стек + код аналогичный рекурсивной функции. Но по своей механике это будет аналог рекурсивной функции и изобретение велосипеда.

Добавлено через 14 минут
COKPOWEHEU, если немного подробнее, то я себе это представляю так.

1. Запускается цикл с начальными значениями (параметры, которые обычно передаются при первом запуске рекурсивной функции) и условием окончания (окончание рекурсии).
2. Запускается блок, моделирующий работу рекурсивной функции (содержит код рекурсивной функции).
3. Как только доходим до места, где надо вызвать рекурсивную функцию, все переменные блока скидываем в стек и задаем новые значения (те, что обычно передаются при рекурсии).
4. Если по окончанию работы блока не выполнен вызов рекурсивной функции, извлекаем из стека последние переменные и снова замыкаем цикл.

Может где не так написал, это все примерно.

Добавлено через 1 минуту
Ну и условием окончания рекурсии будет скорее всего попытка извлечь из стека несуществующие данные.
2
Диссидент
Эксперт C
26970 / 16845 / 3705
Регистрация: 24.12.2010
Сообщений: 37,821
24.11.2017, 17:11 15
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
Все равно не представляю как, скажем, тот же вложенный массив создать без рекурсии или десятка одинаковых функций.
Вы об этом? Создание n-мерного динамического массива
Но в посте 14 там все кратко описано.

Добавлено через 1 минуту
Где-то я и коды соответствующие показывал... Поискать?
0
1365 / 510 / 70
Регистрация: 21.07.2015
Сообщений: 1,290
24.11.2017, 17:58 16
Я никогда не любил рекурсию, даже в универе писал обход деревьев через стек, чем рвал шаблон преподу. В общем случае рекурсивные алгоритмы могут быть значительно короче, но далеко не факт что проще для восприятия и, тем более, для отладки.

Добавлено через 6 минут
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
Не все задачи можно разложить на цикл.
Я может быть открою страшную тайну, но внутри процессора нет никакой рекурсии. И вызовов процедур как таковых тоже нет, вызов процедуры - это положили в стек адрес следующей инструкции и перешли на код процедуры.
1
3505 / 2127 / 395
Регистрация: 09.09.2017
Сообщений: 8,843
24.11.2017, 18:15 17
Команды вызова подпрограммы все-таки есть, а она сама кладет все что надо в стек и переходит по нужному адресу. А значит можно получить и рекурсию. Ручками управлять адресами возврата даже на ассемблере предпочитают не заниматься.
0
Эксперт С++
8711 / 4293 / 956
Регистрация: 15.11.2014
Сообщений: 9,733
24.11.2017, 19:05 18
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
Да ну? Покажите как обычным циклом обойти дерево, да еще с неизвестным заранее количеством ветвей.
это какая то особенная проблема?)
Получить вывод Dir в программу


одна из причин, почему нельзя использовать рекурсию,
и нужно использовать цикл+стек,
проистекает как раз таки из формулировки задачи:
"количестве ветвей дерева - не известно".

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

если же вы, в условиях "неизвестности количестве ветвей"
использовали рекурсию, значит завезли потенциальный баг:
теоретически, ваше ПО в любой момент ляжет лапками к верху,
от переполнения стека.
0
3505 / 2127 / 395
Регистрация: 09.09.2017
Сообщений: 8,843
24.11.2017, 19:17 19
Цитата Сообщение от hoggy Посмотреть сообщение
это какая то особенная проблема?)
Получить вывод Dir в программу
Ну, с ручной эмуляцией рекурсии, наверное, нет.
Цитата Сообщение от hoggy Посмотреть сообщение
рекурсивные алгоритмы можно использовать только тогда,
когда заранее гарантируется (а значит - известно заранее)
некоторая относительно малая и конечная глубина рекурсии.
Обычно это известно хотя бы приближенно.
0
Эксперт С++
8711 / 4293 / 956
Регистрация: 15.11.2014
Сообщений: 9,733
24.11.2017, 19:39 20
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
Обычно это известно хотя бы приближенно.
так вы определитесь.

Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
Покажите как обычным циклом обойти дерево, да еще с неизвестным заранее количеством ветвей.
цемес же в том, что "хотя бы приближенно" - не прокатит.
либо гарантируется, а значит известно точно.
например: максимальная глубина вложенности дерева
не должна превышать какого то фиксированного значения,
иначе считаем, что у нас ошибка выполнения.

либо нужно сразу использовать потенциально безопасные цикл + std::stack.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.11.2017, 19:39
Помогаю со студенческими работами здесь

Реальное применение
Посмотрел я на этот язык, вроде не особо сложный. Но вот вопрос, где его применять кроме мат...

Интерфейсы - их реальное применение в работе
Какой у вас опыт работы с интерфейсами? как их можно использовать так, что бы они были полезными?

Математическая задачка, имеющая реальное практическое применение
Добрый день, уважаемые форумчане. Очередной раз обращаюсь за Вашей помощью. Скажите пожалуйста...

В чем отличие рекурсивных и итерационных вычислений?
В чем отличие рекурсивных и итерационных вычислений?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru