Рекурсия в программировании за и против

Дерево создано с использованием языка программирования Logo и сильно опирается на рекурсию. Каждую ветвь можно рассматривать как уменьшенную версию дерева.

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

[2]

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

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

теории вычислимости доказано, что эти рекурсивные языки являются полными по Тьюрингу; это означает. Что они столь же мощны (их можно использовать для решения тех же задач). Как и императивные языки, основанные на управляющих структурах. Таких как whileи for.

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

оптимизация хвостового вызова.[требуется цитирование]

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

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

Определение рекурсивной функции имеет один или несколько

базовых случаев, означающих входные данные. Для которых функция тривиально(без повторения) выдает результат . И один или несколько рекурсивных случаев, означающих входные данные. Для которых программа повторяется (вызывает себя). Например, факторная функция может быть определена рекурсивно уравнениями 0! = 1 и, для всех n, n! = n(n − 1)! Ни одно из этих уравнений само по себе не является полным определением; первое является базовым случаем. А второе-рекурсивным. Поскольку базовый случай прерывает цепочку рекурсии. Его иногда также называют

Работу рекурсивных случаев можно рассматривать как разбиение сложных входных данных на более простые.

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

Для некоторых функций (например, той. Которая вычисляет ряд для e = 1/0! + 1/1! + 1/2! + 1/3! + …) нет очевидного базового случая. Подразумеваемого входными данными; для них можно добавить

параметр (например. Количество добавляемых терминов в нашем примере серии). Чтобы обеспечить Такой пример более естественно трактуется corecursion,[как?] где последовательные члены в выходных данных являются частичными суммами; это может быть преобразовано в рекурсию с помощью параметра индексирования. Чтобы сказать n-й член (n-я частичная сумма)

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

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

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

Индуктивно определенные данные

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

данные listOfStrings = Пустые | Минусы строки listOfStrings 

Приведенный выше код указывает. Что список строк должен быть либо пустым. Либо структурой. Содержащей строку и список строк.

Самоназвание в определении допускает построение списков любого (конечного) числа строк.

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

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

Аналогично рекурсивные определения часто используются для моделирования структуры выражений и операторов в языках программирования. Языковые конструкторы часто выражают грамматики в синтаксисе. Таком как форма Backus–Naur; вот такая грамматика для простого языка арифметических выражений с умножением и сложением:

 expr>> ::= число>> | (expr> * expr>) | (expr> + expr>) 

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

Коиндуктивно определенные данные и корекурсия

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

Коиндуктивное определение бесконечных потоков струн. Данное неофициально. Может выглядеть следующим образом:

Поток строк это объект ы такой что: голова(ы) - это струна. А хвост(ы) - это поток струн. 

Это очень похоже на индуктивное определение списков строк; разница в том. Что это определение определяет. Как получить доступ к содержимому структуры данных—а именно. Через функции доступа headи tail—и каким может быть это содержимое. Тогда как индуктивное определение определяет. Как создать структуру и из чего она может быть создана.

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

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

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

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

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

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

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

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

Косвенная рекурсия также называется взаимной рекурсией, что является более симметричным термином. Хотя это просто различие акцентов. А не другое понятие. То есть, если Ф вызовов г , а затем г называет Ф, который. В свою очередь. Называет г опять же. С точки зрения Ф одиночку, Ф косвенной рекурсией. В то время как с точки зрения г одиночку. Это косвенно рекурсией. В то время как с точки зрения обеих, Ф И Г являются взаимно рекурсией друг на друга. Аналогично набор из трех или более функций. Вызывающих друг друга. Можно назвать набором взаимно рекурсивных функций.

Анонимный рекурсия

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

Структурная и генеративная рекурсия

Некоторые авторы классифицируют рекурсию как Различие связано с тем. Где рекурсивная процедура получает данные. С которыми она работает. И как она обрабатывает эти данные:

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

Таким образом. Определяющей характеристикой структурно-рекурсивной функции является то. Что аргументом каждого рекурсивного вызова является содержание поля исходного входа. Структурная рекурсия включает в себя почти все обходы деревьев. Включая обработку XML. Создание и поиск двоичного дерева и т. Д. Рассматривая алгебраическую структуру натуральных чисел (то есть натуральное число является либо нулем. Либо преемником натурального числа). Такие функции. Как факториал. Также можно рассматривать как структурную рекурсию.

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

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

Matthias Felleisen, Advanced Functional Programming, 2002[6]

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

  • Можно легко показать. Что все структурно рекурсивные функции на конечных (индуктивно определенных) структурах данных завершаются с помощью структурной индукции: интуитивно каждый рекурсивный вызов получает меньшую часть входных данных. Пока не будет достигнут базовый случай.
  • Генеративно рекурсивные функции, напротив. Не обязательно подают меньший вход для своих рекурсивных вызовов. Поэтому доказательство их завершения не обязательно так же просто. И избегание бесконечных циклов требует большей осторожности. Эти генеративно рекурсивные функции часто могут быть интерпретированы как коррек – турсивные функции – каждый шаг генерирует новые данные. Такие как последовательное приближение в методе Ньютона-и завершение этой корреляции требует. Чтобы данные в конечном итоге удовлетворяли некоторому условию. Которое не обязательно гарантируется.
  • С точки зрения вариантов цикластруктурная рекурсия-это когда существует очевидный вариант цикла . А именно размер или сложность. Который начинается с конечного и уменьшается на каждом рекурсивном шаге.
  • Напротив, генеративная рекурсия — это когда нет такого очевидного варианта цикла. И завершение зависит от функции, такой как

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

Факториал

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

fact(n)={1if n=0nfact(n1)if n>0{\displaystyle \operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}}

Псевдокод (рекурсивный):
факториал функции:
вход: целое число n такое, что n
выход: [n × (n-1) × (n-2) × ... × 1]
1. если n равно 0, верните 1 2. в противном случае верните [ n × факториал(n-1) ]
конечный факториал

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

bn=nbn1{\displaystyle b_{n}=nb_{n-1}}

b0=1{\displaystyle b_{0}=1}

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

Вычисление рекуррентного соотношения для n = 4:
b4 = 4 * b3
= 4 * (3 * b2) = 4 * (3 * (2 * b1)) = 4 * (3 * (2 * (1 * b0))) = 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24

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

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

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

fact(n)=factacc(n,1)factacc(n,t)={tif n=0factacc(n1,nt)if n>0{\displaystyle {\begin{array}{rcl}\operatorname {fact} (n)&=&\operatorname {fact_{acc}} (n,1)\\\operatorname {fact_{acc}} (n,t)&=&{\begin{cases}t&{\mbox{if }}n=0\\\operatorname {fact_{acc}} (n-1,nt)&{\mbox{if }}n>0\\\end{cases}}\end{array}}}

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

Наибольший общий делитель

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

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

gcd(x,y)={xif y=0gcd(y,remainder(x,y))if y>0{\displaystyle \gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\\gcd(y,\operatorname {remainder} (x,y))&{\mbox{if }}y>0\\\end{cases}}}

Псевдокод (рекурсивный):
функция gcd является: входныеданные : целое число x, целое число y такое, что xy
1. если y равно 0, верните x 2. в противном случае верните [ gcd( y, (остаток от x/y) ) ]
конец gcd

Рекуррентное соотношение для наибольшего общего делителя. Где

x%y{\displaystyle x\%y}

выражает остаток от

x/y{\displaystyle x/y}

:

gcd(x,y)=gcd(y,x%y){\displaystyle \gcd(x,y)=\gcd(y,x\%y)}

если

y0{\displaystyle y\neq 0}

gcd(x,0)=x{\displaystyle \gcd(x,0)=x}

Вычисление рекуррентного соотношения для x = 27 и y = 9:
gcd(27, 9) = gcd(9, 27% 9) = gcd(9, 0) = 9 
Вычисление рекуррентного соотношения для x = 111 и y = 259:
ГКД(111, 259) = ГКД(259, 111% 259) = НОД(259, 111) = НОД(111, 259% 111) = НОД(111, 37) = нод(37, 111% 37) = gcd(37, 0) = 37 

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

Псевдокод (итеративный):
функция gcd такова:
вход: целое число x, целое число y такое, что xy и y
1. создайте новую переменную под названием остаток
2. начните цикл 1. если y равно нулю, выйдите из цикла. 2. установите остаток на остаток от x/y 3. установите x в положение y 4. установите y в положение остаток 5. повторите цикл
3. возврат x
end gcd

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

Ханойские башни

Ханойские башни

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

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

hanoi(n)={1if n=12hanoi(n1)+1if n>1{\displaystyle \operatorname {hanoi} (n)={\begin{cases}1&{\mbox{if }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{if }}n>1\\\end{cases}}}

Рекуррентное соотношение для Ханоя:

hn=2hn1+1{\displaystyle h_{n}=2h_{n-1}+1}

h1=1{\displaystyle h_{1}=1}

Вычисление рекуррентного соотношения для n = 4:
ханой(4) = 2*ханой(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 

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

Псевдокод (рекурсивный):
функция:
input: integer n, такая, что n1
1. если n равно 1, то верните 1
2. возврат [2 * [вызов Ханоя(n-1)] + 1]
конец ханою

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

Явная формула для Ханойских башен:
h1 = 1 = 21 - 1 h2 = 3 = 22 - 1 h3 = 7 = 23 - 1 h4 = 15 = 24 - 1 h5 = 31 = 25 - 1 h6 = 63 = 26 - 1 h7 = 127 = 27 - 1 
В общем: hn = 2n

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

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

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

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

 /*  Вызовите binary_search с правильными начальными условиями.  Вход:  данные-это массив целых чисел, отсортированных в порядке возрастания,  найти это число на поиск,  count-общее количество элементов в массиве,  вывод:  результат binary_search  */ инт поиска(инт *данные, int и зрителями, инт граф) { // начало = 0 (начальный индекс) // конец = счетчик - 1 (верхний индекс) вернуться binary_search(сведения, найти, 0, посчитайте,-1); } /*  бинарным поиском.   Вход:  данные-это массив целых чисел, отсортированных в порядке возрастания,  найти такое целое число, чтобы искать,  начать-это минимальное время индекс,  end-максимальный  выходной индекс массива:  положение целого числа toFind в массиве данных,  -1, если не найдено  */ int binary_search(int *data, int toFind, int start, int end) { //Get the midpoint. int mid = start + (end - start)/2; //Integer division //Stop condition. if (start > end) return -1; else if (data[mid] == toFind) //Found? возврат среднего; иначе если (данные[СЧ] > найти) //данных больше, чем найти, поиск нижней части возврата binary_search(сведения, зрителями, начала, середины-1); иначе //данных меньше найти, поиск верхнюю половину вернуть binary_search(сведения, найти, середина+1, конца); } 

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

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

[10]

Примеры в этом разделе иллюстрируют то. Что известно как Этот термин относится к тому. Что рекурсивные процедуры действуют на данные. Которые определены рекурсивно.

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

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

Ниже приведено определение C структуры узла связанного списка. Обратите особое внимание на то. Как узел определяется в терминах самого себя. узла структуры является указателем на другой узел структуры, эффективно создавая тип списка.

struct node { int data; // some integer data struct node *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; // some integer data struct node *left; // указатель на левое поддерево struct node *right; // указатель на правое поддерево }; 

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

// Проверьте, содержит ли tree_node i; верните 1, если да, 0, если нет. int tree_contains(struct node *tree_node, int i) { if (tree_node == NULL) return 0; // base case else if (tree_nodedata == i) return 1; else return tree_contains(tree_nodeleft, i) || tree_contains(tree_noderight, i); } 

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

// Inorder traversal: void tree_print(struct node *tree_node) { if (tree_node != NULL) { // base case tree_print(tree_nodeleft); // go left printf(, tree_nodedata); // print the integer followed by a space tree_print(tree_noderight); // go right } } 

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

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

Поскольку количество файлов в файловой системе может быть различным, рекурсия-единственный практический способ обхода и. Таким образом. Перечисления ее содержимого. Обход файловой системы очень похож на обход дерева, поэтому понятия. Лежащие в основе обхода дерева. Применимы и к обходу файловой системы. Более конкретно. Приведенный ниже код будет примером обхода предзаказа файловой системы.

импорт в Java.интерфейс IO.*; общественный класс файловой системы { публичный статический пустота главный (строка [] аргументы) { траверс (); } /**  * получает файловой системы корней  * выполняет рекурсивный обход файловой системы  */ частный статический недействительным траверс () { файл [] ФС = файл.listRoots (); для (тип int я = 0; я  ПС.длина; я++) { если (ФС[я].isDirectory () && FS и[я].свойство canread ()) { rtraverse (ФС[я]); } } } /**  * рекурсивно переходить по данной директории  *  * @param и ФД указывает начальную точку обхода  */ частный статический недействительным rtraverse (файл ФД) { файл [] ФСС = ФД.файл-список (); для (тип int я = 0; я  ФСС.длина; я++) { системой.из.метод println (ФСС[я]); если (СС[я].isDirectory () && СС[я].свойство canread ()) { rtraverse (ФСС[я]); } } } } 

Этот код смешивает строки. По крайней мере, несколько. Между рекурсией и итерацией. Это, по сути. Рекурсивная реализация. Которая является лучшим способом прохождения файловойсистемы . Это также пример прямой и косвенной рекурсии. Метод Этот пример не нуждается в сценарии

Вопросы реализации

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

  • Функция обертки (вверху)
  • Короткое замыкание базового случая. Известное как
  • Гибридный алгоритм (внизу) – переключение на другой алгоритм после того. Как данные достаточно малы

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

Обертка функции

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

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

Короткое замыкание базового корпуса

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

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

Концептуально короткое замыкание может рассматриваться либо как один и тот же базовый случай и рекурсивный шаг. Только проверяющий базовый случай перед рекурсией. Либо как другой базовый случай (один шаг удален из стандартного базового случая) и более сложный рекурсивный шаг. А именно Поскольку короткое замыкание имеет более сложный поток. По сравнению с четким разделением базового случая и рекурсивного шага в стандартной рекурсии. Его часто считают плохим стилем. Особенно в академических кругах.]

Поиск по глубине

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

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

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

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

  • проверьте значение текущего узла. Верните true. Если совпадение,
  • в противном случае. На потомках. Если не Null. То recurse.

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

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

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

bool tree_contains(struct node *tree_node, int i) { if (tree_node == NULL) return false; // base case else if (tree_nodedata == i) return true; else return tree_contains(tree_nodeleft, i) || tree_contains(tree_noderight, i); } 

Алгоритм короткого замыкания может быть реализован следующим образом:

// Оберточной функции для обработки пустого дерева боол tree_contains(структура узла *tree_node, тип int я) { если (tree_node == значение null) вернуть ложь; // пустое дерево еще вернуться tree_contains_do(tree_node, я); // вызов вспомогательной функции } // предполагается. Tree_node != Нулевое значение bool tree_contains_do(структура узла *tree_node, тип int я) { если (tree_nodeданные == у меня) возврат истина; // нашли другое // рекурсия возврата (tree_nodeслева && tree_contains_do(tree_nodeслева, я)) || (tree_nodeправо && tree_contains_do(tree_nodeправо, я)); } 

Обратите внимание на использование оценки короткого замыкания логических операторов && (И). Так что рекурсивный вызов выполняется только в том случае. Если узел является допустимым (ненулевым). Обратите внимание. Что в то время как первый член в AND является указателем на узел. Второй член является bool. Поэтому общее выражение вычисляется как bool. Это распространенная идиома в рекурсивном коротком замыкании. Это делается в дополнение к оценке короткого замыкания логического оператора || (ИЛИ). Чтобы проверить только правый дочерний элемент. Если левый дочерний элемент терпит неудачу. По сути, весь поток управления все эти функции могут быть заменены одним логическим выражением в операторе return. Но разборчивость не приносит никакой пользы эффективности.

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

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

Рекурсия против итерации

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

Сравните шаблоны для вычисления xn, определенного xn = f(n, xn-1) из xbase:

функция рекурсивная(n) , если n == base return xbase иначе возврат f(n, рекурсивный(n-1)) 
функция итеративная(n) x = xбаза для i = база+1 к n x = f(i, x) возврат x 

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

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

unsigned int factorial(unsigned int n) { unsigned int product = 1; // empty product is 1 while (n) { product *= n; --n; } return product; } 

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

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

И наоборот, все итеративные функции и процедуры. Которые могут быть оценены компьютером (см. Turing completness), могут быть выражены в терминах рекурсивных функций; итеративные управляющие конструкции. Такие как циклы while и for, обычно переписываются в рекурсивной форме в функциональных языках. C, Javaи Python являются известными основными языками. В которых все вызовы функций. Включая хвостовые вызовы может вызывать выделения стека. Что бы не возникнуть. С использованием циклические конструкции; в этих языках. Работаем итеративная программа переписана в рекурсивной форме. Может переполнить стек вызовов, хотя хвост позвонить ликвидации может быть функция. Которая не покрывается языка спецификации и разных реализаций одного и того же языка могут отличаться в хвостовой вызов. Устранение возможности.

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

В языках (например, Си и Ява), которые способствуют итерационные циклические конструкции, там. Как правило. Значительного времени и пространства расходы. Связанные с рекурсивными программами. Из-за затраты. Необходимые для управления стеком и относительной медлительностью вызовов функций; в функциональных языках, функция вызова (особенно в хвостовой вызов), как правило. Очень быстро, и разница. Как правило. Менее заметны.

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

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

В некоторых языках программирования максимальный размер стека вызовов намного меньше. Чем пространство . Доступное в куче, и рекурсивные алгоритмы. Как правило. Требуют больше стекового пространства. Чем итерационные алгоритмы. Следовательно. Эти языки иногда ограничивают глубину рекурсии. Чтобы избежать переполнения стека; Python-один из таких языков.[16] Обратите внимание на приведенное ниже предостережение относительно частного случая хвостовой рекурсии.

Уязвимость

Потому что рекурсивные алгоритмы могут быть предметом стек переполняется. Они могут быть подвержены патологическим или вредоносного ввода.[17] некоторые вредоносные программы специально ориентирована программа стек вызовов и использует стек по определению рекурсивный характер.[18] даже в отсутствии вредоносных программ. Стек переполнения. Вызванное неограниченной рекурсии может быть фатальным для программы, и обработка исключений логика не может допустить соответствующего процесса могут быть прекращены.[19]

Умножение рекурсивных задач

Многократно рекурсивные задачи по своей сути рекурсивны из-за предшествующего состояния. Которое они должны отслеживать. Одним из примеров является обход дерева в качестве поиска по глубине; хотя используются как рекурсивные. Так и итерационные методы[20], они контрастируют с обходом списка и линейным поиском в списке. Который является исключительно рекурсивным и. Следовательно. Естественно итерационным методом. Другие примеры включают алгоритмы Быстрая сортировка, и функции. Такие как функция Аккермана. Все эти алгоритмы могут быть реализованы итеративно с помощью явного стека, но усилия программиста. Связанные с управлением стеком. И сложность результирующей программы, возможно. Перевешивают любые преимущества итеративного решения.

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

Рекурсивные алгоритмы могут быть заменены нерекурсивными аналогами.[21] Одним из методов замены рекурсивных алгоритмов является их моделирование с использованием кучной памяти вместо стековой памяти.[22] Альтернативой является разработка алгоритма замены. Полностью основанного на нерекурсивных методах. Что может быть непросто.Например, рекурсивные алгоритмы для сопоставления подстановочных знаков, такие как алгоритм wildmat РичаСальца. Когда-то былитипичными. Нерекурсивные алгоритмы для той же цели. Такие как алгоритм сопоставления подстановочных знаков Краусса, были разработаны. Чтобы избежать недостатков рекурсии[25] и улучшались только постепенно. Основываясь на таких методах. Как сбор тестов и профилирование производительности.[26]

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

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

Хвостовая рекурсия:Увеличение рекурсии:
//ВВОД: Целые числа x, y такие , что x >= y и y >>= 0>> int gcd(int x, int y) { if (y == 0) return x; else return gcd(y, x % y); } 
//INPUT: n - целое число, такое, что n >= 0> int fact(int n) { if (n == 0) return 1; else return n * fact(n - 1); } 

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

Порядок исполнения

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

Функция 1

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

Recursive1.svg

Функция 2 со сменой строк

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

Recursive2.svg

Время эффективности рекурсивных алгоритмов

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

Правило быстрого доступа (основная теорема)

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

T(n)=aT(n/b)+f(n){\displaystyle T(n)=a\cdot T(n/b)+f(n)}

Тогда Большая О времени-сложность такова:

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

  1. ^
  2. ^ Эпп, Сюзанна (1995). Дискретная математика с приложениями (2-е изд.). ISBN 978-0-53494446-9.
  3. ^ Wirth, Niklaus (1976). Алгоритмы + Структуры данных = Программы. Прентис-Холл, стр. ISBN 978-0-13022418-7.
  4. ^ . www.braveclojure.com. Извлечено 2020-10-21.
  5. ^ Felleisen et al. 2001, art V
  6. ^ b Felleisen. Matthias (2002). . В Jeuring, Johan (ed.). Advanced Functional Programming: 4th International School (PDF). Springer. p. 108. ISBN 9783540448334.
  7. Graham, Knuth & Patashnik 1990, §1.1: The Tower of Hanoi
  8. Эпп 1995, стр. 427-430: Ханойская башня
  9. ^ Epp 1995, pp. 447-448: Явная формула последовательности Ханойской башни
  10. ^ Вирт 1976, с. 127
  11. ^ Монган, Джон; Гигер, Эрик; Киндлер, Ной (2013). Разоблаченные интервью по программированию: Секреты получения вашей следующей работы (3-е изд.). ISBN 978-1-118-26136-1.
  12. ^ Hetland, Magnus Lie (2010), Python Algorithms: Освоение основных алгоритмов на языке Python, Apress, p. 79, ISBN 9781430232384.
  13. ^ Дроздек, Адам (2012), Структуры данных и алгоритмы в C++ (4-е изд.), Cengage Learning, стр. 197, ISBN 9781285415017.
  14. ^ Дрожит, Олин. (PDF). Технологический институт Джорджии. Проверено 2012-09-03.
  15. ^ Лямбда-Конечная. . Лямбда Предельная. 2012-09-03 .
  16. ^ . Docs.python.org… Проверено 2012-09-03.
  17. ^ Krauss, Kirk J. (2014). . Дневник доктора Добба.
  18. ^ Мюллер, Оливер (2012). . Дневник доктора Добба.
  19. ^ . Библиотека классов .NET Framework. Microsoft Developer Network. 2018.
  20. ^ . Технарь Восторг. 2018.
  21. ^ Митрович, Иван. . МыслитеЛьныеработы .
  22. ^ La, Woong Gyu (2015). . Кодовый проект.
  23. ^ Moertel, Tom (2013). .
  24. ^ Salz, Rich (1991). . GitHub.
  25. ^ Krauss, Kirk J. (2008). . Дневник доктора Добба.
  26. ^ Краусс, Кирк Дж. (2018). . Развивайтесь ради производительности.