В комментах некоторые писали что не любят и не используют рекурсию вообще, в частности по причинам указанным выше. Тем не менее, во многих задачах рекурсия - необходимый инструмент, без которого не обойтись, особенно в комбинаторных задачах и всякой целочисленной оптимизации. Я отношусь к ней совершенно нормально и использую довольно часто.
Не так давно, вспоминается, мне довелось использовать совершенно сумасшедший трюк, с которым редко кому приходится сталкиваться - взаимную (или двойную, не знаю как правильно назвать) рекурсию. Это когда функция f1() вызывает функцию f2(), которая в свою очередь вызывает f1() и т.д., такая чехарда, липфроггинг. Дело было в алгоритме паллетизации (трёхмерной упаковки коробок), о котором я писал. Так вот, в алгоритме который я изобрёл, одна часть задачи представляет из себя проблему двумерной упаковки (т.е. множества разных прямоугольников внутри большого прямоугольника размером X на Y. И по вычислительной сложности именно эта часть самая трудная. Для неё мне и пришлось изобретать двойную рекурсию, причём обе рекурсивные функции f1() и f2() сами по себе невероятно сложны. Теоретически может быть всё это можно упаковать без взаимной рекурсии, но наиболее эффективно именно так.
Не буду залезать в подробности, но в этом алгоритме одна рекурсивная функция связана с перебором оставшегося подмножества прямоугольников, другая - с фиксированным набором прямоугольников, но пермутацией позиций предыдущих, уже "упакованных" прямоугольников. И так они вызывают друг друга, пока набор прямоугольников не исчерпается, или пространство не заполнится. Взаимная рекурсия в этой задаче получается очень естественно, и функциональный стек (в Матлабе) выглядит примерно так:
Там ещё миллион разных деталей, тонкостей, исключений, и особых случаев, но в конечном итоге получается красивая плотная упаковка, примерно такая:
Самое удивительное что всё это работает, и очень даже быстро и эффективно, и для очень широкого диапазона всяких случаев. Человек в моей команде, который переписывал это в рабочий код на С++, охал, закатывал глаза и говорил что ничего более сложного ему не приходилось писать. У него ушло на это месяца три, но абсолютное большинство программеров просто не справились бы с этим вообще - это действительно невероятно сложная штука. И это была только одна из задач которые мне нужно было решить в рамках этого проекта.
← Ctrl ← Alt
Ctrl → Alt →
← Ctrl ← Alt
Ctrl → Alt →