Cтраница 1
Нерекурсивная версия позволила бы достичь большей глубины рекурсии, но вывести кривые Серпинского с глубиной больше чем 8 или 9 практически невозможно. Все эти факты определяют преимущество рекурсивного алгоритма. [1]
Сдругой стороны, нерекурсивные версии алгоритмов рисования кривых Гильберта и Серпинского достаточно сложны. [2]
Программа 7.7 представляет собой нерекурсивную версию, построенную на базе рекурсивной версии, представленной в программе 7.6. Поскольку эта программа всегда завершается рекурсивным вызовом самой себя, мы просто восстанавливаем начальные значения параметров и возвращаемся в начало программы. Это значит, что мы отказываемся от рекурсии и не используем стек, а также исключаем из программы вычисления, в которых используется k, и рассматриваем k только как индекс массива. [3]
Следующий код иллюстрирует нерекурсивную версию процедуры рисования кривых Гильберта. [4]
В связи с тем что поиск в глубину играет важную роль в проектировании алгоритмов на графах, представим также нерекурсивную версию процедуры WG. Каждая просмотренная вершина помещается в стек и удаляется из стека после использования. [5]
Хотя этот алгоритм естественно рекурсивен, его довольно просто записать без рекурсии. Поскольку он достаточно прост для понимания, здесь приводится нерекурсивная версия, которая содержит меньше вызовов функции. [6]
Однако для функции BigAddpasimna существенна. Рекурсивная версия исчерпывает память стека при достаточно малых входных значениях. В то время как нерекурсивная версия, вообпр не использующая стек, может вычислить значения суммы для N Ю Ч После этого наступит переполнение для данных типа Double. Конечно, выполнение алгоритма для 10 шагов будет занимать много времени, поэтому поверьте на слово и не экспериментируйте с большими числами. Обратите внимание, что эта функция дает такое же значение, что и функцияN ( N 1) / 2, которую вычислить гораздо проще. [7]
Если имеется алгоритм, который является рекурсивным по своей природе, но вы не уверены, можно ли с помощью рекурсивной версии решить задачу, перепишите ее рекурсивно и выясните это. Проблемы может и не возникнуть. Если какие-либо трудности все же имеются, будет гораздо проще преобразовать рекурсивный алгоритм в нерекурсивную форму, чем сразу создать нерекурсивную версию. [8]
Необоснованное применение рекурсии является не такой очевидной опасностью. Функции вычисления факториала, чисел Фибоначчи, ПОД и BigAdd, представленные ранее, на самом деле не должны быть рекурсивными. Лучшие, нерекурсивные версии этих функций будут описаны позже. [9]
На каждом этапе возникают две задачи по разделению. И только к одной из них мы можем непосредственно сразу же приступить в очередной итерации, другая же заносится в упомянутый список. При этом, конечно, существенно, что требования из списка выполняются несколько специфическим образом, а именно в обратном порядке. Следовательно, первое из перечисленных требований выполняется последним, и наоборот, В приводимой нерекурсивной версии Quicksort каждое требование задается просто левым и правым индексами - это границы части, требующей дальнейшего разделения. Таким образом, мы вводим переменную-массив под именем stack и индекс s, указывающий на самую последнюю строку в стеке ( см. прогр. [10]