Cтраница 4
Эти методы можно легко реализопать с помощью рекурсивной программы, как показано в программе 5.14. которая является непосредственным обобщением программы 5.5 обхода сеянного списка. [46]
Нужно учитывать одну особенность, характерную для рекурсивных программ, подобных той, которую мы использовали для генерации чисел Фибоначчи. [47]
Основная цель этой главы заключается в исследовании рекурсивных программ и структур данных как практических инструментов. Вначале исследуется взаимосвязь между математической рекурсией и простыми рекурсивными программами и приводится ряд примеров применения рекурсии. Затем рассматривается фундаментальная рекурсивная схема, известная под названием разделяй и властвуй, которая используется для решения задач общего характера в нескольких последующих разделах этой книги. После этого приводится общий подход к реализации рекурсивных программ, называемый динамическим программированием, который предоставляет эффективные и элегантные решения для обширного класса задач. Затем подробно рассматриваются деревья, их математические свойства и связанные с ними алгоритмы, в том числе базовые методы обхода дерева ( tree traversal), которые лежат в основе рекурсивных программ обработки деревьев. В завершение будут анализироваться тесно связанные с рекурсией алгоритмы обработки графов - в частности, особое внимание будет уделяться фундаментальной рекурсивной программе поиска в глубину ( depth-first search), которая служит основой для многих алгоритмов обработки графов. [48]
Как отмечалось в главе 5, у каждой рекурсивной программы имеется нерекурсивный аналог, который хотя и выполняет эквивалентные вычисления, тем не менее, он делает это по-другому. Будучи прототипами теории разработки алгоритмов по принципу разделяй и властвуй, нерекурсивные реализации сортировки слиянием заслуживают детального изучения. [49]
Эта йзаовая реалидац я сортировки слиднием йоляегся примером рекурсивной программы. [50]