3.5. Рекурсия 139

Дальнейшие иллюстрации рекурсии

Как мы обсудили выше, рекурсия - понятие определения функции, которая звонит к себе. Когда вызовы функции самостоятельно, мы именуем это как рекурсивный вызов. Мы также полагаем, что функция M рекурсивная, если она вызывает другую функцию, которая в конечном счете приводит к требованию назад к M.

Главная выгода рекурсивного подхода к дизайну алгоритма - то, что он позволяет нам использовать в своих интересах повторную структуру, существующую во многих проблемах. Заставляя наше описание алгоритма эксплуатировать эту повторную структуру рекурсивным способом, мы можем часто избегать сложных исследований случая и вложенных петель. Этот подход может привести к более удобочитаемым описаниям алгоритма, все еще будучи довольно эффективным.

Кроме того, рекурсия - полезный путь к определению объектов, у которых есть повторная подобная структурная форма, такой как в следующих примерах.

Пример 3.1: современные операционные системы определяют справочники файловой системы (которые также иногда называют «папками») рекурсивным способом. А именно, файловая система состоит из справочника верхнего уровня, и содержание этого справочника состоит из файлов и других справочников, которые в свою очередь могут содержать файлы и другие справочники и так далее. Основные справочники в файловой системе содержат только файлы, но при помощи этого рекурсивного определения, операционная система допускает справочники, которые будут вложены произвольно глубоко (как долго, поскольку есть достаточно пространства в памяти).

Пример 3.2: Большая часть синтаксиса на современных языках программирования определена рекурсивным способом. Например, мы можем определить список аргументов в C ++ использование следующего примечания:

список аргументов:

список аргументов аргумента, аргумент

Другими словами, список аргументов состоит или из (i) аргумент или из (ii) argu-ment список, сопровождаемый запятой и аргументом. Таким образом, список аргументов состоит из отделенного от запятой списка аргументов. Точно так же арифметические выражения могут быть определены рекурсивно с точки зрения примитивов (как переменные и константы) и арифметика - metic выражения.

Пример 3.3: есть много примеров рекурсии в искусстве и природе. Один из наиболее классических примеров рекурсии, используемой в искусстве, находится в российских куклах Matryoshka. Каждая кукла сделана из цельного дерева или полая и содержит другую куклу Matryoshka в нем.

140 Глава 3. Множества, связанные списки и рекурсия

3.5.1 Линейная рекурсия

Самая простая форма рекурсии - линейная рекурсия, где функция определена

так, чтобы это сделало самое большее один рекурсивный звонок каждый раз, когда это призвано. Этот тип рекурсии полезен, когда мы рассматриваем алгоритмическую проблему с точки зрения первого или последнего элемента плюс остающийся набор, у которого есть та же самая структура как оригинальный набор.

Подведение итогов элементов множества рекурсивно

Предположим, например, нам дают множество, A, n целых чисел, которые мы хотим суммировать

вместе. Мы можем решить эту проблему суммирования, используя линейную рекурсию, наблюдая

то, что сумма всех n целых чисел в A равна [0], если n = 1, или сумма первого n-

1 целое число в плюс последний элемент в A. В частности мы можем решить это суммирование

проблема используя рекурсивный алгоритм, описанный в Кодовом Фрагменте 3.38.

Алгоритм LinearSum (A, n):

Вход: множество целого числа A и целое число n³ 1, такой, что у A есть, по крайней мере, n элементы

Продукция: сумма первых n целых чисел в A

если n = 1 тогда

возвратитесь [0]

еще

возвратите LinearSum (A, n- 1) + [n- 1]

Кодовый Фрагмент 3.38: Подведение итогов элементов во множестве, используя линейную рекурсию.

Этот пример также иллюстрирует важную собственность, которой рекурсивная функция должна всегда обладать - функция заканчивается. Мы гарантируем это, сочиняя не - рекурсивное заявление для случая n = 1. Кроме того, мы всегда выполняем рекурсивное

обратитесь к меньшей ценности параметра (n- 1), чем то, что нам дают (n), таким образом,

это, в некоторый момент (в «основании» рекурсии), мы выполним nonre-

рукописная часть вычисления (возвращающийся [0]). В целом у алгоритма, который использует линейную рекурсию, как правило, есть следующая форма:

• Тест на основные случаи. Мы начинаем, проверяя на ряд основных случаев (там должен

будьте по крайней мере одним). Эти основные случаи должны быть определены так, чтобы каждое возможное

цепь рекурсивных вызовов в конечном счете достигает основного случая, и обработка каждого основного случая не должна использовать рекурсию.

• Повториться. После тестирования на основные случаи мы тогда выполняем единственный рекурсивный вызов.

Этот рекурсивный шаг может включить тест, который решает который из нескольких возможных

рекурсивные вызовы сделать, но это в конечном счете должно сделать только один из этих звонков каждый раз, когда мы выполняем этот шаг. Кроме того, мы должны определить каждый возможный рекурсивный вызов так, чтобы он сделал успехи к основному случаю.