Рекурсия (информатика)

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

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

Большинство компьютеров языков программирования язык рекурсию, позволяя функции вызывать себя из собственного кода. Некоторые языки функционального программирования (например, Clojure ) не определяют никаких циклических конструкций, а полагаются исключительно на рекурсию для многократного вызова кода. В теории вычислимости доказано, что эти рекурсивные языки полны по Тьюрингу ; это означает, что они такие же проблемы (их можно использовать для решения тех же проблем), что и императивные языки, основанные на управляющих структурах, таких как , в то время каки для.

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

Содержание

• 1 Рекурсивные функции и алгоритмы
• 2 Рекурсивные функции
  • 2.1 Индуктивно воспроизведенные данные
  • 2.2 Совместно стандартные данные и коркурсия
• 3 Типы рекурсии
  • 3.1 Одиночная рекурсия и множественная рекурсия
  • 3.2 Косвенная рекурсия
  • 3.3 Анонимная рекурсия
  • 3.4 Сравнение структурной и генеративной рекурсии
• 4 Рекурсивные программы
  • 4.1 Рекурсивные процедуры
    • 4.1.1 Факториал
    • 4.1.2 На большой общий делитель
    • 4.1.3 Ханойские башни
    • 4.1.4 Двоичный поиск
  • 4.2 Рекурсивные структуры данных (структурная рекурсия)
    • 4.2.1 Связанные списки
    • 4.2.2 Двоичные деревья
    • 4.2.3 Обход файловой системы
• 5 Проблемы реализации
  • 5.1 Функция оболочки
  • 5.2 Короткое замыкание базового случая
    • 5.2.1 Поиск в глубину
  • 5.3 Гибридный горитм
• 6 Рекурсия и итерация
  • 6.1 Выразительная сила
  • 6.2 Проблемы с производительностью
  • 6.3 Размер стека
  • 6.4 Уязвимость
  • 6.5 Множественные ре сивные проблемы
  • 6.6 Рефакторинг рекурсии
• 7 Хвост- рекурсивные функции
• 8 Порядок выполнения
  • 8.1 Функция 1
  • 8.2 Функция 2 с переставленными строками
• 9 Эффективность рекурсивных алгоритмов
  • 9.1 Краткое правило (основная теорема)
• 10 См. также
• 11 Ссылки
• 12 Дополнительная литература
• 13 Внешние ссылки

Рекурсивные функции и алгоритмы

Распространенная тактика компьютерного программирования - разделить проблему на подзадачи того же типа, что и исходный, решите эти подзадачи и объедините результаты. Это часто называют методом разделяй и властвуй ; в сочетании с таблицами поиска , в которой хранятся результаты решения подзадач (чтобы избежать их многократного решения и увеличения времени вычислений), это можно назвать динамическим программированием или мемоизация.

Определение рекурсивной функции имеет один или несколько базовых случаев, то есть есть входные данные, для которых функция выдает результат тривиально (без повторения), и один или несколько рекурсивных случаев, что означает ввод (ы) для программы повторения (вызывает себя). Например, функция факториала может быть определена рекурсивно уравнениями 0! = 1 и для всех n>0 n! = п (п - 1)!. Ни одно уравнение само по себе не составляет полного определения; первый - базовый, второй - рекурсивный. Временный базовый случай разрывает цепочку рекурсии, его иногда также называют «завершающим случаем».

Работа с рекурсивными случаями можно рассматривать как разбиение сложных входных данных на более простые. В спроектированной рекурсивной функции при каждом рекурсивном вызове проблема ввода должна быть упрощена таким образом, чтобы в итоге был достигнут базовый случай правильно. (Функции, которые не предназначены для завершения при нормальных обстоятельствах - например, некоторые системные и серверные процессы являются исключением из этого правила.) Пренебрежение написано базовым вариантом или его неправильное тестирование может вызвать бесконечный цикл.

Для некоторых функций (например, для вычислений серии для e = 1/0! + 1/1! + 1/2! + 1/3! +...) входные данные не подразумевают очевидного базового случая; для них можно добавить параметр (например, добавляемых терминов в нашем примере серии), чтобы использовать количество «критерий остановки», который устанавливает базовый случай. Такой пример более естественно в corecursion, где последовательные члены выходных данных являются частичными суммами; это можно преобразовать в рекурсию, используя параметр индексации, чтобы сказать «вычислить n-й член (n-я частичная сумма)».

Рекурсивные типы данных

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

Индуктивно конец данные

Индуктивно конец рекурсивные определения данных - это определение, которое указывает, как создать экземпляры данных. Например, связанные списки могут быть определены индуктивно (здесь с использованием синтаксиса Haskell ):

data ListOfStrings = EmptyList | Минусы String ListOfStrings

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

Другим примером индуктивного определения являются натуральные числа (или положительные целые ):

Натуральное число - это либо 1 или n + 1, где n - натуральное число.

Подобным же образом рекурсивные определения часто используются для моделирования структур выражений и операторов на языках программирования. Разработчики языков часто выражают грамматики в синтаксисе, таком как форма Бэкуса - Наура ; вот такая грамматика для простого языка арифметических выражений с умножением и сложением:

:: = | (* ) | (+ )

Это означает, что выражение является либо числовым, либо произведением двух выражений, либо суммой двух выражений. Рекурсивно выражением во второй и третьей строках, грамматика допускает произвольно сложные арифметические выражения, такие как (5 * (( 3 * 6) + 8)), с более чем одним произведением или суммой в одном выражении.

Коиндуктивно современные данные и коркурс

Коиндуктивная определение данных - это определение, которое является операцией

Совместное определение бесконечных потоков строк, заданных неформально, может выглядеть так:

Это очень похоже на индуктивное определение списков строк; разница в том, что это определение указывает, как получить доступ к c с одержание структуры данных - а именно, с помощью функций доступа headи tail- и каким может быть это содержимое, тогда как индуктивное определение указывает, как создать структуру и из чего она может быть создана.

Corecursion к коиндукции и может относиться к конкретным экземпляров (возможно) бесконечных объектов. Как метод программирования, он наиболее часто используется в контексте ленивых языков программирования и может быть предпочтительнее рекурсии, когда желаемый размер или точность вывода программы неизвестны. В таких случаях требуется программа как определение бесконечно большого (или бесконечно точного) результата, так и механизм для достижения конечной части этого результата. Проблема первых вычислений n простых чисел может быть решена с помощью курсивной программы (например, здесь ).

Типы рекурсии

Одиночная рекурсия и множественная рекурсия

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

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

Множественная рекурсия иногда может быть преобразована в одиночную рекурсию (и, при желании, оттуда в итерацию). Например, в то время как вычисление Фибоначчи наивно представляет многократную итерацию, поскольку каждое значение требует двух предыдущих значений, оно может быть вычислено с помощью одной рекурсии, передав два последовательных значения в качестве параметров. Это более естественно оформлено как corecursion, построение из начальных значений, отслеживание на каждом шаге двух последовательных значений - см. corecursion: примеры. Более сложный пример - использование многопоточного двоичного дерева, допускает итеративный обход дерева, а не множественную рекурсию.

Косвенная рекурсия

Основные примеры рекурсии и основных примеров, представленных здесь, демонстрируют ую рекурсию, в которой функция вызывает сама себя. Косвенная рекурсия, вызывается функция не сама по себе, другая функция, которую она вызвала (когда прямо или косвенно). Например, если вызывает f, это прямая рекурсия, но если f вызывает g, который вызывает, то это косвенная рекурсия f. Возможны цепочки из трех и более функций; например, функция 1 вызывает функцию 2, функция 2 вызывает функцию 3, функция 3 снова вызывает функцию 1.

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

Анонимная рекурсия

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

Структурная рекурсия по сравнению с генеративной рекурсией

Некоторые авторы классифицируют рекурсию как «структурную» или «порождающую». Различие связано с тем, где рекурсивная получает данные, которые она работает, и как она обрабатывает эти данные:

[Функции, потребляющие структурированные данные] обычно разбивают свои аргументы на их непосредственные структурные компоненты, а обрабатывают эти компоненты. Если один из непосредственных компонентов принадлежит к тому же классу данных, что и ввод, функция является рекурсивной. По этой причине мы называем эти функции (СТРУКТУРНО) РЕКУРСИВНЫМИ ФУНКЦИЯМИ.

Таким образом, определяющая характеристика структурно рекурсивная функция заключается в том, что является аргументом каждого рекурсивного вызова содержимого поля ввода. Структурная рекурсия включает в себя почти все обходы дерева, включая обработку XML, создание и поиск двоичного дерева и т. Д. Учитывая алгебраическую структуру натуральных чисел (то есть, такое число равно нулю или является преемником натурального числа), такие функции как факториал также можно рассматривать как структурную рекурсию.

Генеративная рекурсия - альтернатива:

Многие хорошо известные рекурсивные алгоритмы генерируют совершенно новый фрагмент данных из заданных данных и повторяются на нем. HtDP (Как разрабатывать программы) относится к этому виду как генеративная рекурсия. Примеры генеративной рекурсии: gcd, quicksort, двоичный поиск, mergesort, метод Ньютона, фракталы и адаптивная интеграция.

Это различие важно в доказательстве завершения функции.

• Все структурно рекурсивные функции на конечных (индуктивно определенных ) структурах данных может быть легко реализованы с помощью структурной индукции : интуитивно каждый рекурсивный вызов получает меньший фрагмент входных данных, до тех пор, пока не будет достигнут базовый случай.
• Генеративно-рекурсивные функции, напротив, не обязательно передают меньший ввод в свои рекурсивные вызовы, поэтому доказательство их завершения не обязательно так просто и позволяет избежать бесконечных циклов требует большей осторожности. Эти генеративно-рекурсивные функции часто можно интерпретировать как коркурсивные функции - каждый шаг генерирует новые данные, такие как последовательное приближение в методе Ньютона - и для завершения этого коркурсивного курса требуется, чтобы данные в конечном итоге удовлетворяли некоторому условию, которое не обязательно гарантировано.
• С точки зрения вариантов цикла, структурная рекурсия - это когда существует очевидный вариант цикла, а именно размер или сложность, которая начинается с конечных значений и уменьшается на каждом рекурсивном шаге.
• Напряжение, генеративная рекурсия - это когда нет такого очевидного противостояния цикла, а завершение зависит от функций, как «ошибка приближения», которая не обязательно уменьшается до нуля, и, таким образом, завершение не гарантируется без дальнейшего анализа.

Рекурсивные программы

Рекурсивные процедуры

Факториал

Классическим примером рекурсивной процедуры является функция, используемая для вычислений факториала натурального числа :

$факт\; \; (n)\; =\; \{1,\; если\; n\; =\; 0,\; n\; \cdot \; факт\; \; (n\; -\; 1),\; если\; n>0,\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{fact\}\; (n)\; =\; \{\backslash \; begin\; \{cases\}\; 1\; \{\backslash \; t\_dv\; \{if\}\}\; n\; =\; 0\; \backslash \backslash \; n\; \backslash \; cdot\; \backslash \; operatorname\; \{fact\}\; (n-1)\; \{\backslash \; t\_dv\; \{if\}\}\; n>0\; \backslash \backslash \backslash \; end\; \{cases\}\}\}$

функция факториал:. вход : целое число n такое, что n>= 0. output : [n × (n-1) × (n-2) ×… × 1]. 1. если n равно 0, return 1 2. в случае потери return [n × факториал (n-1)]. конец факториал

Функция также может быть записано как рекуррентное соотноше ваше :

$bn\; =\; nbn\; -\; 1\; \{\backslash \; displaystyle\; b\_\; \{n\}\; =\; nb\_\; \{n-1\}\}$

$b\; 0\; =\; 1\; \{\backslash \; displaystyle\; b\_\; \{0\}\; =\; 1\}$

Эта оценка рекуррентного отношения представет вычисление, которое будет выполнено при оценке псевдокода выше:

b4= 4 * b 3. = 4 * (3 * b 2) = 4 * (3 * (2 * b 1)) = 4 * (3 * (2 * (1 * b 0))) = 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24

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

функция факториал:. input : целое число n такое, что n>= 0. вывод : [n × (n-1) × (n-2) ×… × 1]. 1. создать новую переменную с именем running_total со значением 1. 2. начало цикл 1. если n равно 0, выход цикл 2. установить для running_total значение (running_total × n) 3. декремент n 4. повторить цикл. 3. return running_total. end factorial

Приведенный выше императивный код эквивалентен этому математическому определению с использованием аккумуляторной переменной t:

$fact\; \; (n)\; =\; factacc\; \; (n,\; 1)\; factacc\; \; (n,\; t)\; =\; \{t,\; если\; n\; =\; 0\; factacc\; \; (n\; -\; 1,\; nt),\; если\; n>0,\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{rcl\}\; \backslash \; operatorname\; \{fact\}\; (n)\; =\; \backslash \; operatorname\; \{fact\_\; \{acc\}\}\; (n,\; 1)\; \backslash \backslash \backslash \; operatorname\; \{fact\_\; \{acc\}\}\; (n,\; t)\; =\; \{\backslash \; begin\; \{cases\}\; t\; \{\backslash \; t\_dv\; \{if\}\}\; n\; =\; 0\; \backslash \backslash \backslash \; operatorname\; \{fact\_\; \{acc\}\}\; (n-1,\; nt)\; \{\backslash \; t\_dv\; \{if\}\}\; n>0\; \backslash \backslash \backslash \; end\; \{cases\}\}\; \backslash \; end\; \{array\}\}\}$

Приведенное выше определение напрямую переводится на языки функционального программирования, такие как Схема ; это пример рекурсивной итерации.

Самый распространенный divisor

алгор итм Евклида, который вычисляет g Наибольший общий делитель двух целых чисел может быть записан рекурсивно.

Определение функции:

$НОД\; (x,\; y)\; =\; \{x,\; если\; y\; =\; 0\; gcd\; (y,\; остаток\; \; (x,\; y)),\; если\; y>0\; \{\backslash \; displaystyle\; \backslash \; gcd\; (x,\; y)\; =\; \{\backslash \; begin\; \{cases\}\; x\; \{\backslash \; t\_dv\; \{if\}\}\; y\; =\; 0\; \backslash \backslash \backslash \; gcd\; (y,\; \backslash \; operatorname\; \{elseder\}\; (x,\; y))\; \{\backslash \; t\_dv\; \{if\}\}\; y>0\; \backslash \backslash \; \backslash \; end\; \{cases\}\}\}$

функция gcd: input : целое число x, целое число y такое, что x>0 и y>= 0. 1. если y равно 0, вернет x 2. в противном случае вернет [gcd (y, (остаток от x / y))]. end gcd

отношение повторяемости для наибольшего общего делителя, где $x\%\; y\; \{\backslash \; displaystyle\; x\; \backslash \%\; y\}$выражает остаток от $x\; /\; y\; \{\backslash \; displaystyle\; x\; /\; y\}$:

$gcd\; (x,\; y)\; =\; gcd\; (y,\; x\%\; y)\; \{\backslash \; displaystyle\; \backslash \; gcd\; (x,\; y)\; =\; \backslash \; gcd\; (\; y,\; x\; \backslash \%\; y)\}$если $y\; \ne \; 0\; \{\backslash \; disp\; laystyley\; \backslash \; neq\; 0\}$

$gcd\; (x,\; 0)\; =\; x\; \{\backslash \; displaystyle\; \backslash \; gcd\; (x,\; 0)\; =\; x\}$

gcd ( 27, 9) = gcd (9, 27% 9) = gcd (9, 0) = 9

gcd (111, 259) = gcd (259, 111% 259) = gcd (259, 111) = gcd (111, 259% 111) = gcd (111, 37) = gcd (37, 111% 37) = gcd (37, 0) = 37

Рекурсивная программа выше - это хвостовая рекурсия ; он эквивалентен итерационному алгоритму, и вычисление, показанное выше, показывает этапы оценки, которые запускают хвостовые вызовы языка. Ниже представлена ​​версия того же алгоритма с явной итерацией, подход для языка, который не исключает хвостовые вызовы. Сохраняя свое состояние полностью в число x и y и используя конструкцию цикла, программа избегает выполнения рекурсивных циклов и увеличения стека цикла.

функция gcd:. input : целое число x, целое число y такое, что x>= y и y>= 0. 1. создать новую переменную с именем остаток. 2. начало цикла 1. если y равно нулю, выйти из цикла 2. установить остаток на остаток от x / y 3. x в y 4. установить y в остаток 5. повторить цикл. 3. return x. end gcd

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

Башни Ханоя

Башни Ханоя - математическая головоломка, решение которой иллюстрирует рекурсию. Есть три колышка, на которых можно удерживать стопки дисков разного диаметра. Диск большего размера нельзя ставить поверх меньшего. Начиная с n дисков на одной привязке, их необходимо перемещать на другую привязку к очереди. Какое наименьшее количество шагов для перемещения стека?

Определение функций:

$hanoi\; \; (n)\; =\; \{1,\; если\; n\; =\; 1\; 2\; \cdot \; hanoi\; \; (n\; -\; 1)\; +\; 1,\; если\; n>1\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{hanoi\}\; (\; n)\; =\; \{\backslash \; begin\; \{cases\}\; 1\; \{\backslash \; t\_dv\; \{if\}\}\; n\; =\; 1\; \backslash \backslash \; 2\; \backslash \; cdot\; \backslash \; operatorname\; \{hanoi\}\; (n-1)\; +1\; \{\backslash \; t\_dv\; \{if\}\}\; n>1\; \backslash \; \backslash \backslash \; end\; \{case\}\}\}$

Соотношение повторяемости для hanoi:

$hn\; =\; 2\; hn\; -\; 1\; +\; 1\; \{\backslash \; displaystyle\; h\_\; \{n\}\; =\; 2h\_\; \{n-1\}\; +1\}$

$h\; 1\; =\; 1\; \{\backslash \; displaystyle\; h\_\; \{1\}\; =\; 1\}$

hanoi (4) = 2 * hanoi (3) + 1 = 2 * (2 * ханой (2) + 1) + 1 = 2 * (2 * (2 * ханой (1) + 1) + 1) + 1 = 2 * (2 * (2 * 1 + 1) + 1) + 1 = 2 * (2 * (3) + 1) + 1 = 2 * (7) + 1 = 15

.

Примеры реализации:

функция hanoi:. input : целое число n, такое, что n>= 1. 1. если n равн о 1, вернуть 1. 2. return [2 * [вызов ханоя (n-1)] + 1]. end hanoi

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

h1= 1 = 2-1 ч 2 = 3 = 2-1 ч 3 = 7 = 2-1 ч 4 = 15 = 2-1 ÷ 5 = 31 = 2-1 h 6 = 63 = 2-1 h 7 = 127 = 2 -1

В общем: h n = 2-1, для всех n>= 1

Двоичный поиск

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

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

Пример реализации двоичного поиска в C:

/ * Вызов binary_search с правильными начальными условиями. INPUT: данные - это массив целых чисел, СОРТИРУЕМЫЙ в возрастании, toFind - это целое число для поиска, count - общее количество элементов в массиве OUTPUT: результат binary_search * / int search (int * data, int toFind, int count) {/ / Start = 0 (начальный индекс) // End = count - 1 (верхний индекс) return binary_search (data, toFind, 0, count-1); } / * Алгоритм двоичного поиска. ВХОД: данные - это массив целых чисел, СОРТИРУЕМЫЙ в порядке возрастания, toFind - это целое число для поиска, начало - это минимальный индекс массива, конец - это максимальный индекс массива. ВЫВОД: позиция целого числа, toFind в массиве данных, -1, если не найдено. * / int binary_search (int * data, int toFind, int start, int end) {// Получаем среднюю точку. int mid = начало + (конец - начало) / 2; // Целочисленное деление // Условие остановки. если (начало>конец) возврат -1; else if (data [mid] == toFind) // Нашли? возврат в середине; else if (data [mid]>toFind) // Данные больше, toFind, поиск в нижней половине return binary_search (data, toFind, start, mid-1); else // Данные меньше, чем toFind, поиск в верхней части return binary_search (data, toFind, mid + 1, end); }

Рекурсивные структуры данных (структурная рекурсия)

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

«Рекурсивные алгоритмы особенно подходят, когда основная проблема или обрабатываемые данные используемые в рекурсивных терминах».

Примеры в этом разделе иллюстрируют то, что известно как «структурная рекурсия». Этот относится к тому факту, что рекурсивные процедуры воздействуют на данные, которые рекурсивно используются.

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

Связанные списки

Ниже приведено определение структуры узла связанного списка. Обратите внимание на то, как узел связан сам по себе. «Следующий» элемент структуры узла - это указатель на другой узел структуры, создающий тип списка.

struct node {int data; // некоторый узел структуры целочисленных данных * next; // указатель на другой узел структуры};

Механизм структуры данных установлены рекурсивно, процедуры, которые работают с ней, могут быть реализованы естественным образом как рекурсивные процедуры. Процедура list_print, определенная ниже, просматривает список до тех пор, пока список не станет пустым (то есть указатель списка не будет иметь значение NULL). Для каждого узла он печатает элемент данных (целое число). В реализации C список остается неизменным процедурой list_print.

void list_print (struct node * list) {if (list! = NULL) // базовый вариант {printf ("% d", list->data); // печать целочисленных данных, за которую следует пробел list_print (list->next); // рекурсивный вызов следующего узла}

Двоичные деревья

Ниже представлены простое определение двоичного дерева. Как и узел для связанных списков, он определяется сам по себе рекурсивно. Есть два самореферентных указателя: левый (указывающий на левое поддерево) и правый (указывающий на правое поддерево).

struct node {int data; // некоторый узел структуры целочисленных данных * left; // указатель на левое поддерево struct node * right; // указываем на правое поддерево};

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

// Проверяем, содержит ли tree_node i; вернуть 1, если это так, 0 в противном случае. int tree_contains (struct node * tree_node, int i) {if (tree_node == NULL) return 0; // базовый случай else if (tree_node->data == i) return 1; иначе вернуть tree_contains (tree_node->left, i) || tree_contains (tree_node->right, i); }

Для любого данного вызова tree_contains, как определено выше, будет выполнено не более двух рекурсивных вызовов.

// Обход inorder: void tree_print (struct node * tree_node) {if (tree_node! = NULL) {// базовый случай tree_print (tree_node->left); // идти налево printf ("% d", tree_node->data); // выводим целое число, за которым следует пробел tree_print (tree_node->right); // идем вправо}}

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

Обход файловой системы

Газ количество файлов в файловой системе может различаться, рекурсия - единственный практический способ пройти и таким образом, перечислить ее содержимое. Обход файловой системы очень похож на обход дерева, поэтому концепция обхода дерева применимы к обходу файловой системы. В частности, приведенный ниже код может быть примером обхода перед порядком файловой системы.

импортировать java.io. *; общедоступный класс Файловая система {общедоступный статический void main (String args) {traverse (); } / ** * Получает корни файловой системы * Продолжает рекурсивный обход файловой системы * / private static void traverse () {File fs = File.listRoots (); for (int i = 0; i < fs.length; i++) { if (fs[i].isDirectory () fs[i].canRead ()) { rtraverse (fs[i]); } } } /** * Recursively traverse a given directory * * @param fd indicates the starting point of traversal */ private static void rtraverse (File fd) { File fss = fd.listFiles (); for (int i = 0; i < fss.length; i++) { System.out.println (fss[i]); if (fss[i].isDirectory () fss[i].canRead ()) { rtraverse (fss[i]); } } } }

Этот код, по крайней мере, частично смешивает строки между рекурсией и итерацией. Это, по сути, рекурсивная реализация, которая является лучшим способом пройти по файловая Метод "rtraverse" является прямым прямым примером; метод "traverse" является прямым прямым примером; метод "traverse" является косвенным, который вызывает "rtraverse". В этом примере не требуется "базовый случай" из-за того, что

Проблемы реализации

В реальной реализации, а не чисто рекурсивная функция, а не чисто рекурсивная функция (одиночная проверка базового случая, в полном рекурсивном шаге) в данной файловой системе всегда будет какое-то фиксированное количество файлов или каталогов. К ним:

• функция оболочки (вверху)
• Короткое замыкание базового случая, ака «Рекурсия длины руки» (внизу)
• Гибридный алгоритм внизу (внизу) - переключение на другой алгоритм, когда данные малы ru ough

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

Функция-оболочка

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

Функции-программирование их Программу 1 задания (чтобы рекурсивная функция могла пропускать), выполнение инициализации (выделение памяти, инициализации), особенно для числа, таких как «уровень рекурсии» или частичных вычислений для мемоизация, и обработать исключение и ошибки. На языках, поддерживающих вложенные функции, вспомогательная функция может быть вложена внутри функции-оболочки и использовать общую область видимости. В отсутствие вложенных функций вспомогательные функции вместо этого являются отдельной функцией, если возможно, частной (поскольку они не вызываются напрямую), а информация передается функции-оболочке с помощью передачи по ссылке.

Short- обход базового случая

Замыкание базового варианта, также известное как рекурсия длины руки, заключается в проверке базового случая перед выполнением рекурсивного вызова, т. е. проверкой следующего вызова будет базовым случаем, вместо вызова и последующей проверки базового случая. Короткое замыкание делается, в частности, из соображений эффективности, чтобы избежать накладных расходов на вызов функции, который немедленно возвращается. Обратите внимание, что, поскольку базовый случай уже был проверен (непосредственно перед рекурсивным шагом), его не нужно проверять отдельно, но нужно использовать функцию-оболочку для случая, когда общая рекурсия начинается с базового случая. сам. Например, в функции факториала базовый случай равен 0! = 1, при этом сразу возвращается 1 вместо 1! это короткое замыкание, может пропустить 0; это можно смягчить с помощью функции-оболочки.

Короткое замыкание в первую очередь вызывает беспокойство, когда встречается много базовых случаев, таких как нулевые указатели в дереве, которые могут быть линейными по количеству вызовов функций, что обеспечивает значительную экономию для алгоритмов O (n); это показано ниже для поиска в глубину. Короткое замыкание на дереве соответствует рассмотрению листа (непустого узла без дочерних элементов) в качестве базового случая, а не рассмотрения пустого узла в качестве базового случая. Если есть только один базовый случай, например, при вычислении факториала, короткое замыкание обеспечивает только экономию O (1).

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

Поиск в глубину

Базовый пример короткого замыкания дается в поиске в глубину (DFS) двоичного дерева; стандартное рекурсивное обсуждение см. в разделе бинарные деревья.

Стандартный рекурсивный алгоритм для DFS:

• базовый случай: если текущий узел равен Null, вернуть false
• рекурсивный шаг: в случае проверить значение текущего узла, вернуть true, если совпадение, в в противном случае рекурсивно для дочерних элементов

При коротком замыкании это вместо этого:

• проверяет текущий узел, возвращает истину, если совпадение,
• в случае потери, для дочерних элементов, если не NULL, то рекурсивно.

Что касается стандартных шагов, это перемещает проверку базового случая перед рекурсивным шагом. В качестве альтернативы их можно рассматривать как другую форму базового случая и рекурсивного шага соответственно. Обратите внимание, что для этого требуется функция-оболочка для обработки случая, когда само дерево пусто (этот узел имеет значение Null).

В случае совершенного двоичного дерева высоты h, в качестве дочерних узлов имеется 2-1 узел и 2 нулевых указателя (по 2 для каждого из 2 листьев), поэтому короткое замыкание сокращает количество функций вдвое в худшем случае.

В C стандартный рекурсивный алгоритм может быть реализован как:

bool tree_contains (struct node * tree_node, int i) {if (tree_node == NULL) return false; // базовый случай else if (tree_node->data == i) return true; иначе вернуть tree_contains (tree_node->left, i) || tree_contains (tree_node->right, i); }

Сокращенный алгоритм может быть реализован как:

// Функция-оболочка для обработки пустого дерева bool tree_contains (struct node * tree_node, int i) {if (tree_node == NULL) return false; // пустое дерево иначе return tree_contains_do (tree_node, i); // вызов вспомогательной функции} // Предполагается, что tree_node! = NULL bool tree_contains_do (struct node * tree_node, int i) {if (tree_node->data == i) return true; // найдено еще // рекурсивный возврат (tree_node->left tree_contains_do (tree_node->left, i)) || (tree_node->right tree_contains_do (tree_node->right, i)); }

Обратите внимание на использование оценки короткого замыкания логических операторов (AND), так что рекурсивный вызов выполняется только в том случае, если узел действителен (не равенство Null). Обратите внимание, что в то время как первый член AND является указателем на узел, поэтому второе выражение оценивается как логическое значение. Это обычная идиома в рекурсивном коротком замыкании. Это дополнение к оценке короткого замыкания логического || (ИЛИ), чтобы проверять только правый дочерний элемент, если левый дочерний элемент не работает. Фактически, весь поток управления эти функции могут быть заменен одним логическим выражением в операторе возврата, но разборчивость не влияет на эффективность.

Гибридный алгоритм

Рекурсивные алгоритмы часто неэффективны для небольших данных из-за накладных расходов, связанных с повторными вызовами функций и возвратами. По этой причине эффективные реализации рекурсивных алгоритмов часто начинаются с рекурсивного алгоритма, но затем переключаются на другой алгоритм, когда входной сигнал становится небольшим. Важным примером является сортировка слиянием, которая часто реализуется путем переключения нерекурсивной сортировкой вставкой, когда данные достаточно малы, как в мозаичной сортировке слиянием. Гибридные рекурсивные алгоритмы часто могут быть дополнительно доработаны, как в Timsort, полученном из гибридной сортировки слиянием / сортировкой вставкой.

Сравнение рекурсии и итерации

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

шаблон для вычислений x n определенный как x n = f (n, x n-1) из x base :

функция рекурсивная (n) if n == base return x base else return f (n, рекурсивная (n-1))

итеративная функция (n) x = x base для i = base + 1 до nx = f (i, x) return x

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

Например, функция факториал может быть реализована итеративно в C путем выполнения стандартного образца аккумулятора, не путем передачи аргументов и значений возврата с помощью рекурсия:

беззнаковое int факториал (unsigned int n) {unsigned int product = 1; // пустой продукт равенство 1 while (n) {product * = n; --n; } вернуть товар; }

Выразительная сила

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

И наоборот, все итерационные функции и процедуры, которые могут быть оценены компьютером (см. Полнота по Тьюрингу ), могут быть выражены в терминах рекурсивных функций; Конструкции итеративного управления, такие как циклы while и для циклов, обычно переписываются в рекурсивной форме на функциональных языках. Однако на практике это переписывание зависит от исключение хвостового вызова, что характерно не для всех языков. C, Java и Python - основные известные языки, в которых используются все вызовы функций, включая хвостовые вызовы, могут вызывать выделение стека, чего не было при использовании циклических конструкций. ; на этих языках рабочая итеративная программа, переписанная в рекурсивной форме, может переполнять стековые программы, хотя устранение хвостового вызова может быть функция, которая не охвачена спецификацией языка, и реализации одного и того же языка могут отличаться в возможностях устранения хвостового вызова.

Проблемы с производительностью

На языках (таких как C и Java ), которые предпочитают конструкции итеративного цикла, обычно связанные с большими временными и пространственными затратами. с рекурсивными программами из-за накладных расходов, необходимых для управления стеком, и относительной медленности функций функций; в функциональных языках вызов функции (особенно хвостовой вызов ) обычно является очень быстрой операцией, и обычно разница менее заметна.

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

Пространство стека

На некоторых языках программирования максимальный размер стека требуется намного меньше, чем пространство, доступное в куче, и рекурсивные алгоритмы обычно требуют больше места в стеке, чем итерационные алгоритмы. Следовательно, эти языки иногда устанавливают ограничение на глубину рекурсии, чтобы избежать переполнения стека ; Python - один из таких языков. Обратите внимание на предостережение ниже относительно особого случая хвостовой рекурсии.

Уязвимости

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

Множественно-рекурсивные проблемы

Множественно-рекурсивные проблемы по своей сути рекурсивны, поскольку их необходимо отслеживать из-за состояния предыдущего состояния. Одним из примеров является обход дерева, как в поиск в глубину ; хотя используются как рекурсивные, так и итерационные методы, они контрастируют с обходом по списку и линейным поиском в списке, который является однократно рекурсивным и, следовательно, естественным итеративным методом. Другие примеры включают в себя алгоритмы «разделяй и властвуй», такие как Quicksort, и такие функции, как функция Аккермана. Все эти алгоритмы могут быть реализованы итеративно с помощью стека , но усилия программиста, связанные с управлением стеком, и сложность полученной программы, возможно, перевешивают любые преимущества итеративного решения.

Рефакторинг рекурсии

Рекурсивные алгоритмы могут быть заменены нерекурсивными аналогами. Одним из методов замены рекурсивных алгоритмов является их имитация с использованием динамической памяти вместо стековой памяти. Альтернативой является разработка алгоритма замены, полностью основанного на нерекурсивных методах, что может быть применено. Например, рекурсивные алгоритмы для сопоставления подстановочных знаков, такие как алгоритм Рич Зальца 'подстановочные, когда-то были типичными. Были разработаны алгоритмы сопоставления подстановочных знаков Краусса, были разработаны алгоритмы сопоставления подстановочных знаков, чтобы избежать недостатков рекурсии, улучшились постепенно на основе таких методов, как сбор тестов и профилирование производительности.

Хвостовые рекурсивные функции

Хвостовые рекурсивные функции - это функции, все рекурсивные вызовы представляют собой хвостовыми вызовами и, следовательно, не наращивать любые отложенные операции. Например функция, gcd (снова показанная ниже) является хвостовой рекурсивной. Напротив, факториальная функция (также ниже) не хвостовая рекурсия; поскольку его рекурсивный вызов не находится в хвостовой позиции, он создает указанные операции после завершения рекурсивного вызова. С компилятором или интерпретатором, который обрабатывает хвостовые рекурсивные вызовы как переходы, а не вызовы функций, хвостовая рекурсивная функция, такая как gcd, будет работать с использованием постоянного пространства. Таким образом, программа по сути является итеративной, что эквивалентно использованию структурного управления императивного языка.

// ВХОД: целые числа x, y такие, что x>= y и y>= 0 int gcd (int x, int y) {if (y == 0) вернуть x; иначе вернуть gcd (y, x% y); }

// ВХОД: n - целое число, такое что n>= 0 int fact (int n) {if (n == 0) return 1; иначе вернуть n * факт (n - 1); }

Значение хвостовой рекурсии заключается в том, что при выполнении любого рекурсивного хвоста (или любого хвостового вызова) позиция возврата вызывающего абонента не должна сохраняться в стеке вызова ; когда рекурсивный вызов возвращается, он будет переходить непосредственно к ранее сохраненной позиции возврат. Следовательно, распознают это свойство хвостовых каналов, хвостовая рекурсия экономит и пространство, и время.

Порядок выполнения

В простом случае, когда функция вызывает себя только один раз, инструкции, помещенные перед рекурсивным вызовом, выполняются один раз за рекурсию перед любыми инструкциями, размещенными после рекурсивного вызова. Последние выполняются повторно после достижения максимальной рекурсии. Рассмотрим следующий пример:

Функция 1

void recursiveFunction (int num) {printf ("% d \ n", num); if (num < 4) recursiveFunction(num + 1); }

Функция 2 с переставленными строками

void recursiveFunction (int num) {if (num < 4) recursiveFunction(num + 1); printf("%d\n", num); }

Эффективность времени рекурсивных алгоритмов

Эффективность времени рекурсивного алгоритмы могут быть выражены в рекуррентном отношении нотации Big O. Затем их можно (обычно) упростить до одного члена Big-O.

Краткое правило (основная теорема)

Если временная сложность имеет вид

$T\; (n)\; =\; a\; \cdot \; T\; (n\; /\; b)\; +\; f\; (n)\; \{\backslash \; displaystyle\; T\; (n)\; =\; a\; \backslash \; cdot\; T\; (n\; /\; b)\; +\; f\; (n)\; \}$

Тогда Большой O временной сложности будет таким:

• Если $f\; (n)\; =\; O\; (n\; log\; b\; \; a\; -\; ϵ)\; \{\backslash \; displaystyle\; f\; (n)\; =\; O\; (n\; ^\; \{\backslash \; log\; \_\; \{b\}\; a-\; \backslash \; epsilon\})\}$для некоторой константы $ϵ>0\; \{\backslash \; displaystyle\; \backslash \; epsilon>0\}$, тогда $T\; (n)\; =\; \Theta \; (n\; log\; b\; \; a)\; \{\; \backslash \; Displaystyle\; Т\; (п)\; =\; \backslash \; тета\; (п\; ^\; \{\backslash \; ло\; g\; \_\; \{b\}\; a\})\}$
• Если $f\; (п)\; =\; \Theta \; (n\; журнал\; b\; \; a)\; \{\backslash \; displaystyle\; f\; (n)\; =\; \backslash \; Theta\; (n\; ^\; \{\backslash \; log\; \_\; \{b\}\; a)\; \})\}$, затем $T\; (n)\; =\; \Theta \; (n\; журнал\; б\; \; журнал\; \; n)\; \{\backslash \; Displaystyle\; T\; (n)\; =\; \backslash \; Theta\; (n\; ^\; \{\backslash \; log\; \_\; \{b\}\; a\; \}\; \backslash \; log\; n)\}$
• Если $f\; (n)\; =\; \Omega \; (n\; log\; b\; \; a\; +\; ϵ)\; \{\backslash \; displaystyle\; f\; (n)\; =\; \backslash \; Omega\; (n\; ^\; \{\backslash \; log\; \_\; \{b\}\; a\; +\; \backslash \; epsilon\})\}$для некоторой константы $ϵ>0\; \{\backslash \; displaystyle\; \backslash \; epsilon>0\}$, и если $a\; \cdot \; f\; (n\; /\; b)\; \le \; c\; \cdot \; f\; (n)\; \{\backslash \; displaystyle\; a\; \backslash \; cdot\; f\; (n\; /\; b)\; \backslash \; leq\; c\; \backslash \; cdot\; f\; (n)\}$для некоторой константы c < 1 and all sufficiently large n, then $T\; (n)\; =\; \Theta \; (f\; (n))\; \{\backslash \; displaystyle\; T\; (n)\; =\; \backslash \; Theta\; (f\; (n))\}$

где a представляет количество рекурсивных показателей на каждом уровне рекурсии, b представляет, во сколько раз меньше ввод для следующего уровня рекурсии (т.е. количество частей, которые на вы делите задачу), а f (n) представляет работу, функцию которую выполняет независимо от какой-либо рекурсии (например, разбиение, рекомбинирование) на каждом уровне рекурсии.

См. Также

• Функциональное программирование
• Иерархические и рекурсивные запросы в SQL
• Парадокс Клини - Россера
• Открытая рекурсия
• Рекурсия
• Кривая Серпинского
• Функция Маккарти 91
• μ-рекурсивные функции
• Примитивные рекурсивные функции
• Tak (функция)

Ссылки

Дополнительная литература

• Бэррон, Дэвид Уильям (1968) [1967]. Написано в Кембридже, Великобритания. Гилл, Стэнли (ред.). Рекурсивные техники в программировании. Компьютерные монографии Макдональда (1-е изд.). Лондон, Великобритания: Macdonald Co. (Publishers) Ltd. SBN 356-02201-3.(viii + 64 страницы)
• Рубио-Санчес, Мануэль (2017). Введение в рекурсивное программирование. CRC Нажмите. ISBN 978-1-351-64717-5.
• Певац, Ирена (2016). Практика рекурсии в Java. CreateSpace Независимый. ISBN 978-1-5327-1227-2.
• Робертс, Эрик (2005). Рекурсивное мышление с помощью Java. Уайли. ISBN 978-0-47170146-0.
• Рол, Джеффри С. (1984). Рекурсия через Паскаль. Издательство Кембриджского университета. ISBN 978-0-521-26934-6.
• Хелман, Пол; Верофф, Роберт. Стены и зеркала.
• Абельсон, Гарольд ; Сассман, Джеральд Джей ; Суссман, Джули (1996). Структура и интерпретация компьютерных программ (2-е изд.). MIT Нажмите. ISBN 0-262-51087-1.
• Дейкстра, Эдсгер У. (1960). «Рекурсивное программирование». Numerische Mathematik. 2 (1): 312–318. doi : 10.1007 / BF01386232.

ние ссылки