Kirill Pankratov (neznaika_nalune) wrote,
Kirill Pankratov
neznaika_nalune

Рекурсивное

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

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

Не так давно, вспоминается, мне довелось использовать совершенно сумасшедший трюк, с которым редко кому приходится сталкиваться - взаимную (или двойную, не знаю как правильно назвать) рекурсию. Это когда функция f1() вызывает функцию f2(), которая в свою очередь вызывает f1() и т.д., такая чехарда, липфроггинг. Дело было в алгоритме паллетизации (трёхмерной упаковки коробок), о котором я писал. Так вот, в алгоритме который я изобрёл, одна часть задачи представляет из себя проблему двумерной упаковки (т.е. множества разных прямоугольников внутри большого прямоугольника размером X на Y. И по вычислительной сложности именно эта часть самая трудная. Для неё мне и пришлось изобретать двойную рекурсию, причём обе рекурсивные функции f1() и f2() сами по себе невероятно сложны. Теоретически может быть всё это можно упаковать без взаимной рекурсии, но наиболее эффективно именно так.

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


Там ещё миллион разных деталей, тонкостей, исключений, и особых случаев, но в конечном итоге получается красивая плотная упаковка, примерно такая:


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

  • "Going postal" - Кучно пошло

    Очередные пострелушки - теперь в Индианаполисе, в офисе Fedex, 8 убитых.…

  • Апрельская зима по расписанию

    16 апреля 2021 - более 10 см снега. Повторяется прошлогодняя история почти день в день, тогда было 18 апреля. И примерно так почти каждый год в…

  • Байденские - 2

    Политика США зарабатывает на дозу сыну президента Байдена - вполне подходящий заголовок, по мотивам по мотивам публикации в британской Daily Mail.…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 50 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →

  • "Going postal" - Кучно пошло

    Очередные пострелушки - теперь в Индианаполисе, в офисе Fedex, 8 убитых.…

  • Апрельская зима по расписанию

    16 апреля 2021 - более 10 см снега. Повторяется прошлогодняя история почти день в день, тогда было 18 апреля. И примерно так почти каждый год в…

  • Байденские - 2

    Политика США зарабатывает на дозу сыну президента Байдена - вполне подходящий заголовок, по мотивам по мотивам публикации в британской Daily Mail.…