Рекурсивный подход

Cтраница 1

Рекурсивный подход обычно предпочитается итеративному в тех случаях, когда рекурсия более естественно отражает математическую сторону задачи и приводит к программе, которая проще для понимания и отладки. Другой причиной для выбора рекурсивного решения является то, что итеративное решение может не быть очевидным. [1]

Рекурсивный подход полезен прежде всего для алгоритмов на графах ( см. разд. [2]

Обычно рекурсивный подход предпочитают итеративному, если он более естественно отражает задачу и ее результаты, то есть более нагляден и легче отлаживается. Другая причина предпочтения рекурсивного решения состоит в том, что итеративное решение может не быть очевидным. [3]

Используя рекурсивный подход, аналогичный программе 13.6, реализуйте операции construct, search и insert для таблиц символов, в основе которых лежат структуры данных в виде сбалансированных по высоте ( AVL) деревьев. [4]

Используя RB-представление и рекурсивный подход, аналогичный программе 13.6, реализуйте операции construct, search и insert для таблиц символов, в основе которых лежат структуры данных в виде восходящих сбалансированных 2 - 3 - 4-деревьев. Совет: код может выглядеть аналогично программе 13.6, но должен выполнять операции в другом порядке. [6]

Используя RB - представление и рекурсивный подход, аналогичный программе ] 3.6, ревизуйте операции construct t № urch к / iufrt ии та & шц t и мнило в, ь основе которых лежат структуры данных ь виде вое ходя а дик сбгизнснршнишмк деревьев, С и: кат может ьыглддеть анпогичтю программе 13, ft, nn выполнять операции в другом порядке. [7]

Некоторые неприятности могут поджидать любителей рекурсивного подхода к написанию функции. Возможны, в принципе, ситуации, когда рекурсивные вызовы переполнят внутренний стек данных сопроцессора, рассчитанный на восемь уровней рекурсии, и возникнет сбой программы. [8]

Решение не всякой проблемы выигрывает от использования рекурсивного подхода, а порой и невозможно применить рекурсию. Однако если Вы в состоянии управлять списком LIFO в любом виде, то Ваша задача по существу является рекурсивной. Даже в том случае, когда рекурсия невозможна, целесообразно выполнить первоначальный вариант в виде рекурсивной программы, затем отбросить рекурсию, моделируя LIFO-память с помощью Ваших собственных связанных списков или индексированных структур данных. Полученная в результате программа будет гораздо яснее и проще для понимания, чем в случае ее разработки с пустого места. [9]

Программа, иллюстрирующая области действия ( часть 2 из 2. [10]

Сначала мы рассмотрим рекурсию обобщенно, а затем исследуем несколько программ, содержащих рекурсивные функции. Рекурсивные подходы к решению задач имеют ряд общих элементов. Для решения задачи вызывается рекурсивная функция. Фактически функция знает решение только простейшего случая ( случаев), или так называемого основного случая. Если функция вызывается для решения основного случая, то она просто возвращает результат. Если функция вызывается для решения более сложной проблемы, функция делит задачу на две обобщенных части: часть, для которой функция имеет способ решения, и часть, для которой функция решения не имеет. Чтобы сделать рекурсию возможной, последняя часть должна быть похожа на первоначальную задачу, но она должна быть более простым, или редуцированным ее вариантом. Поскольку эта новая задача похожа на первоначальную, функция запускает ( вызывает) свою новую копию, чтобы продолжить решение меньшей задачи. Этот процесс называется рекурсивным вызовом или шагом рекурсии. [11]

Эту программу было бы трудно понять без двух уровней абстракции, разработанных для ее реализации. Несложно убедиться, что рекурсивный подход реализует ротации, изображенные на рис. 13.17; затем можно убедиться, что программа реализует высокоуровневый алгоритм в 2 - 3 - 4-деревьях - разделяет 4-узлы на пути вниз по дереву, а затем вставляет новый элемент в 2 - или 3-узел в месте завершения пути поиска в нижней части дерева. [12]

Лисп входит в число наиболее значимых и долговечных языков программирования. Его влияние на исследования в области искусственного интеллекта и технологии знаний особенно проявилось в интерактивном программировании, методах функционального программирования, в распространении в программировании идей рекурсивного подхода, а также в том, что многие идеи в последствии были включены Китайский в более новые языки программирования. [13]

Страницы: 1