Основная цель этой главы заключается в исследовании рекурсивных программ и структур данных как практических инструментов. ... - Большая Энциклопедия Нефти и Газа
Выдержка из книги
Седжвик Р.N.
Фундаментальные алгоритмы на с++ Части1-4
Основная цель этой главы заключается в исследовании рекурсивных программ и структур данных как практических инструментов. Вначале исследуется взаимосвязь между математической рекурсией и простыми рекурсивными программами и приводится ряд примеров применения рекурсии. Затем рассматривается фундаментальная рекурсивная схема, известная под названием разделяй и властвуй, которая используется для решения задач общего характера в нескольких последующих разделах этой книги. После этого приводится общий подход к реализации рекурсивных программ, называемый динамическим программированием, который предоставляет эффективные и элегантные решения для обширного класса задач. Затем подробно рассматриваются деревья, их математические свойства и связанные с ними алгоритмы, в том числе базовые методы обхода дерева ( tree traversal), которые лежат в основе рекурсивных программ обработки деревьев. В завершение будут анализироваться тесно связанные с рекурсией алгоритмы обработки графов - в частности, особое внимание будет уделяться фундаментальной рекурсивной программе поиска в глубину ( depth-first search), которая служит основой для многих алгоритмов обработки графов.