Рекурсивный алгоритм

Cтраница 1

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

Рекурсивный алгоритм - это алгоритм, решающий задачу путем решения одного или нескольких более узких вариантов той же задачи. Для реализации рекурсивных алгоритмов в C используются рекурсивные функции - функции, которые вызывают самих себя. Рекурсивные функции в C соответствуют рекурсивным определениям математических функций. Изучение рекурсии начнем с исследования программ, которые непосредственно вычисляют математические функции. Как будет показано, базовые механизмы можно расширить, что приведет к обобщенной парадигме программирования. [2]

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

Некоторые рекурсивные алгоритмы настолько сложны, что применение этих методов затруднено или невозможно. Проблематично создать нерекурсивные алгоритмы для рисования кривых Гильберта и Серпинского. [4]

Этот рекурсивный алгоритм использует системный стек для отслеживания текущей вершины графа, что позволяет правильно осуществить возвращение, наткнувшись на тупик. Вы можете построить аналогичный нерекурсивный алгоритм самостоятельно, воспользовавшись стеком для занесения туда и удаления пройденных вершин графа. [5]

Реализация рекурсивного алгоритма для двоичного дерева в языке Модула-2 особенно проста благодаря применению типа указателя, динамических элементов данных и рекурсивных обращений к процедурам. [6]

Идея рекурсивного алгоритма не вызывает трудностей. [7]

Насколько эффективен рекурсивный алгоритм. Сможем ли мы подсчитать его эффективность, если будем знать, что алгоритм непосредственного вычисления квадратичен, разбиение входных данных логарифмично, а объединение решений линейно ( все в зависимости от размеров входных данных) 4, и что входные данные разбиваются на восемь частей, размер каждой из которых равен четверти исходного. Эту задачу не так-то легко решить, не очень-то понятно даже, как к ней приступать. Однако оказывается, что анализ алгоритмов вида разделяй и властвуй очень прост, если шаги Вашего алгоритма поставлены в соответствие шагам предложенного выше общего алгоритма этого вида: непосредственное вычисление, разбиение входа, некоторое количество рекурсивных вызовов и объединение полученных решений. [8]

Лемма 5.2 Рекурсивный алгоритм разделяй и властвуй решения задачи о ханойских башнях дает решение, приводящее к 2 - 1 перемещениям. [9]

С помощью рекурсивного алгоритма не создается никаких копий исходного массива V; все действие совершается пересылкой для указания того, какая часть V должна быть реорганизована на данном шаге. Эго означает, что единственной областью внешней памяти, необходимой для быстрой сортировки, является область для стека границ массива, описывающих еще не подвергшиеся разбиению множества. Легко показать, что если на каждом шаге быстрая сортировка осуществляется сначала с меньшим подмножеством, а потом с большим, то стек никогда не будет глубже, чем 1о § 2 N. Даже для N 106 Iog2 N 20, поэтому такой дополнительный объем требуемой памяти незначителен. [10]

Архитектура специального программного обеспечения. [11]

ФОРТРАН программирование рекурсивных алгоритмов требует использования специальных приемов, усложняющих программу. [12]

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

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

К сожалению, рекурсивный алгоритм для под счета чисел Фибоначчи содержит не только хвостовую рекурсию. Алгоритм использует два рекурсивных обращения для вычисления значения. Второй вызов следует после завершения первого. Поскольку первый вызов находится не в самом конце функции, это не хвостовая рекурсия, поэтому ее нельзя удалить обычным способом. [15]

Страницы: 1 2 3 4