Cтраница 2
Создайте функцию, которая решает задачу о ранце методом нисходящего динамического программирования, но используя при этом рекурсивное решение, основывающееся на вычислении оптимального количества конкретного элемента, который должен быть помещен в ранец, исходя из определения ( рекурсивно) оптимального способа упаковки ранца без этого элемента. [16]
Рациональность GPS может быть подвержена сомнению по двум причинам: а) молчаливо предполагается, что свойства, для которых вычисляются различия, в достаточной степени независимы друг от друга ( этим гарантируется, что при уменьшении различий по одному из признаков не происходит его увеличения по другим); б) если к данному состоянию не применим некоторый оператор, то попытка применить к этому же состоянию другой оператор представляется по меньшей мере столь же рациональной, как и рекурсивное решение начать весь поиск сначала. GPS не продемонстрировал пока сколько-нибудь убедительно преимущество второго предположения. Эрнст и Ньюэлл [10] опубликовали аргументированное исследование, посвященное применению GPS в 11 различных задачах. [17]
Базовые операции search, insert и sort для BST-деревьев легко реализовать и выполнить даже при весьма незначительной случайности в последовательности операций, поэтому BST-деревья широко используются применительно к динамическим таблицам символов. Они допускают также простые рекурсивные решения для поддержки других видов операций, как было показано в этой главе на примере операций select, remove и join, и как будет показано во многих примерах далее в книге. [18]
Обычно рекурсивный подход предпочитают итеративному, если он более естественно отражает задачу и ее результаты, то есть более нагляден и легче отлаживается. Другая причина предпочтения рекурсивного решения состоит в том, что итеративное решение может не быть очевидным. [19]
Рекурсивный подход обычно предпочитается итеративному в тех случаях, когда рекурсия более естественно отражает математическую сторону задачи и приводит к программе, которая проще для понимания и отладки. Другой причиной для выбора рекурсивного решения является то, что итеративное решение может не быть очевидным. [20]
Есть тема, которую часто опускают во вводных курсах программирования, хотя она и играет важную концептуальную роль во многих алгоритмах - это рекурсия. Поэтому мы посвящаем третью главу рекурсивным решениям. В ней показано, что рекурсия - обобщение понятия повторения ( итерации), и как таковая она представляет собой важную и мощную концепцию программирования. К несчастью, во многих курсах программирования рекурсия используется в примерах, где достаточно простой итерации. [21]
Краевое условие рекурсивного отношения называют также рекурсивным базисом. К выбору ограничения для рекурсивного отношения и соответствующего ему программного утверждения нужно отнестись очень внимательно. Имея дело с задачей, допускающей рекурсивное решение, следует придерживаться следующих принципов. [22]
Однако, этот подход имеет один скрытый недостаток, о котором следует помнить. Как должно быть понятно из примеров, приведенных на рис. 5.1 - 5.3, при выполнении рекурсивной программы вызовы функций вкладываются один в другой, пока не будет достигнута точка, когда вместо рекурсивного вызова выполняется возврат. В большинстве сред программирования такие вложенные вызовы функций реализуются с помощью эквивалента встроенных стеков. В общем случае глубина будет зависеть от вводимых данных. При использовании рекурсивной программы следует учитывать, что среда программирования должна поддерживать стек, размер которого пропорционален глубине рекурсии. При решении сложных задач необходимый для этого стека объем памяти может заставить отказаться от использования рекурсивного решения. [23]