November 14th, 2013

la

Рекурсивное

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

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

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

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


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