@Nijat19
Люблю математику

Используются ли рекурсивные алгоритмы в олимпиадах по программированию?

Читал что рекурсивные алгоритмы медленнее итерационных. Заметна ли разница?
  • Вопрос задан
  • 372 просмотра
Решения вопроса 1
wataru
@wataru
По заголовку: Рекурсивные алгоритмы используются очень часто.

Если то же самое решение можно написать чисто итерационно, то так будет быстрее, но не намного. Я не помню ни одного случая, когда условное переписывание с DFS на BFS побороло бы time limit. Больше скорости можно выиграть просто развернув циклы в правильную сторону, чтобы в кэш попадать.

Кроме того, довольно часто единственное итеративное решение подразумевает ручную реализацию стека и может быть даже медленнее чисто рекурсивного решения. И писать его дольше и налажать можно дополнительно где.

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

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

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

Есть только один важный момент - размер стека. Если у вас может быть 100000 рекурсивных вызовов, то в стандартный размер стека это счастье не влезет и программа упадет с runtime error. Не знаю, как сейчас, подкручен ли размер стека на этапе компиляции. Но в свое время мы всегда увеличивали размер стека в C++ через ```“#pragma comment(linker, ”/STACK:2000000“)``` или что-то подобное.
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
@Mercury13
Программист на «си с крестами» и не только
В разы, но не на порядок. Скорее всего, задача впишется в ограничение по времени.

Дополнение. О рекуррентных соотношениях я говорю, что методы решения от лучшего к худшему такие:
1. Преобразовать соотношение так, чтобы получить меньшую глубину рекурсии или даже прямое вычисление.
2. Динамическое программирование — если мы способны восстановить порядок вычисления и при этом не наделать много лишних вычислений.
3. Рекурсивное с доказательством, что одно и то же дважды не вычислим.
4. Рекурсивное с кэшированием.
5. Рекурсивное какое попало.

Кроме того, динамическое программирование на ациклическом направленном графе общего вида будет, скорее всего, рекурсивным, и переписывание его под программный стек будет даже медленнее!
Ответ написан
twobomb
@twobomb
Иногда без рекурсии никак, на олимпиадах можешь использовать все что угодно, главное чтобы в итоге твоя программа вложилась в ограничение по времени выполнения и использование памяти.
Ответ написан
firedragon
@firedragon
Senior .NET developer
На олимпиадах принципиально не разрешают переписывать код и пользоваться отладчиком?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы