Cтраница 4
Как было показано в главе 5, алгоритмы с одним рекурсивным вызовом могут быть сведены к циклу, но алгоритмы с двумя рекурсивными циклами, подобные сортировке слиянием или быстрой сортировке, открывают двери в мир алгоритмов типа разделяй и властвуй и древовидных структур, в котором отводится место и для наших лучших алгоритмов. Сортировка слиянием и быстрая сортировка заслуживают тщательного изучения не только из-за их важного практического значения, но и в силу того, что они позволяют глубже погрузиться в сущность рекурсии, которая может сослужить добрую службу при разработке и понимании других рекурсивных алгоритмов. [46]
Приведенное определение предиката length не соответствует хвостовой рекурсии, потому что рекурсивный вызов не является последним шагом в своем предложении. [47]
На короткое время мы пренебрежем параметрами и будем считать, что рекурсивные вызовы не допускаются. В эту категорию попадают блоки в языках с блочной структурой, а также подпрограммы в Фортране и Коболе. [48]
Таким образом, для получения функции трудоемкости необходим детальный анализ дерева рекурсивных вызовов, результатом которого должно быть количество внутренних ( порождающих рекурсию) вершин дерева - Уг ( п) и количество листьев дерева - Vi ( n), связанных с остановом рекурсии. [49]
Пример обработки префиксного выражения программой 5.4 показан на рис. 5.3. Множество рекурсивных вызовов маскируют сложную серию вычислений. Подобно большинству рекурсивных программ, работу этой программы проще всего понять, воспользовавшись методом индукции: полагая, что она работает правильно применительно к простым выражениям, можно предположить, что это справедливо и применительно к сложным выражениям. Программа представляет собой простой пример рекурсивного нисходящего анализатора - аналогичный процесс используется для преобразования программ C в машинные коды. [50]
Действия, связанные с такой проверкой, уже не могут содержать рекурсивных вызовов. Если это условие не будет выполняться, то глубина рекурсии станет бесконечной, что неизбежно приведет к аварийному останову программы. [51]