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

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

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

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

-  Никлаус Вирт , Алгоритмы + структуры данных = программы , 1976 ^[3]

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

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

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

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

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

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

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

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

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

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

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

данные  ListOfStrings  =  EmptyList  |  Минусы  String  ListOfStrings

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

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

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

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

 < выражение >  :: =  < число > | ( < выражение > * < выражение > ) | ( < выражение > + < выражение > )

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

Совместно определенные данные и коркурс [ править ]

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

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

Поток строк - это такой объект, что: head (s) - это строка, а tail (s) - это поток строк.

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

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

Типы рекурсии [ править ]

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

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

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

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

Косвенная рекурсия [ править ]

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

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

Анонимная рекурсия [ править ]

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

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

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

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

-  Фелляйзен, Финдлер, Флатт и Кришнаурти, Как разрабатывать программы , 2001 ^[5]

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

Альтернативой является генеративная рекурсия :

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

-  Маттиас Фелляйзен, Расширенное функциональное программирование , 2002 ^[6]

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

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

Рекурсивные программы [ править ]

Рекурсивные процедуры [ править ]

Факториал [ править ]

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

${\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 > = 0 
вывод : [ n × ( n -1) × ( n -2) ×… × 1] 
 1. если n равно 0, вернуть 1 2. в противном случае верните [ n × факториал ( n -1)] 
конечный факториал.

Функцию также можно записать как рекуррентное отношение :

${\displaystyle b_{n}=nb_{n-1}}$

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

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

б 4 = 4 * б 3
 = 4 * (3 * б 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

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

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

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

${\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 ; это пример рекурсивной итерации.

Наибольший общий делитель [ править ]

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

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

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

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

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

${\displaystyle \gcd(x,y)=\gcd(y,x\%y)}$ если ${\displaystyle y\neq 0}$

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

gcd (27, 9) = gcd (9, 27% 9) = НОД (9, 0) = 9

gcd (111, 259) = gcd (259, 111% 259) = НОД (259, 111) = НОД (111, 259% 111) = НОД (111, 37) = НОД (37; 111% 37) = НОД (37, 0) = 37

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

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

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

Башни Ханоя [ править ]

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

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

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

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

${\displaystyle h_{n}=2h_{n-1}+1}$

${\displaystyle h_{1}=1}$

ханой (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

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

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

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

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

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

Двоичный поиск [ править ]

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

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

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

 / *  Вызвать binary_search с правильными начальными условиями. ВХОД:  данные - это массив целых чисел, СОРТИРУЕМЫЙ в порядке  возрастания , toFind - это целое число для поиска,  count - общее количество элементов в массиве. ВЫХОД:  результат binary_search* /  int  search ( int  * data ,  int  toFind ,  int  count )  {  // Start = 0 (начальный индекс)  // End = count - 1 (верхний индекс)  return  binary_search ( data ,  toFind ,  0 ,  count -1 );  } / *  Алгоритм двоичного поиска. ВХОД:  данные - это массив целых чисел, СОРТИРУЕМЫЙ в порядке  возрастания , toFind - это целое число для поиска,  start - это минимальный индекс массива,  end - это максимальный индекс массива.  ВЫВОД:  позиция целого числа 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 );  еще // Данные меньше, чем toFind, поиск в верхней половине  return  binary_search ( data ,  toFind ,  mid + 1 ,  end );  }

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

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

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

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

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

Связанные списки [ править ]

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

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 -> право ,  i ); }

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

// Обход в порядке : 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 );  // идем направо  } }

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

Обход файловой системы [ править ]

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

import  java.io. * ;public  class  FileSystem  {общедоступный  статический  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 ] ); } } }/ **  * Рекурсивно перемещаться по заданному каталогу  *  * @param fd указывает начальную точку обхода  * / private  static  void  rtraverse  ( File  fd )  { File  []  fss  =  fd . listFiles  ();for  ( int  i  =  0 ;  i  <  fss . length ;  i ++ )  { System . из . println  ( fss [ i ] ); если  ( fss [ i ] . isDirectory  ()  &&  fss [ i ] . canRead  ())  { rtraverse  ( fss [ i ] ); } } }}

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

Проблемы реализации [ править ]

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

• Функция обертки (вверху)
• Замыкание базового случая, также известного как "Рекурсия на длину руки" (внизу)
• Гибридный алгоритм (внизу) - переключение на другой алгоритм, когда объем данных достаточно мал

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

Функция оболочки [ править ]

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

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

Замыкание базового случая [ править ]

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

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

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

Поиск в глубину [ править ]

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

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

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

Вместо этого при коротком замыкании:

• проверить значение текущего узла, вернуть истину, если совпадение,
• в противном случае для потомков, если не Null, то рекурсивно.

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

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

В 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 ;  // пустое дерево  else  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( узел_дерева -> вправо ,  i )); }

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

Гибридный алгоритм [ править ]

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

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

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

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

функция рекурсивная (n) если n == base вернуть x базу еще return f (n, рекурсивный (n-1)) 

функция итеративная (n) х = х основание для i = base + от 1 до n х = е (я, х) вернуть х

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

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

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

Выразительная сила [ править ]

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

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

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

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

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

Пространство стека [ править ]

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

Уязвимость [ править ]

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

Множественные рекурсивные задачи [ править ]

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

Рефакторинг рекурсии [ править ]

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

Хвостовые рекурсивные функции [ править ]

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

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

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

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

Порядок исполнения [ править ]

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

Функция 1 [ править ]

недействительная  рекурсивная функция ( целое  число )  {  printf ( "% d \ n " ,  число );  если  ( число  <  4 )  рекурсивная функция ( число  +  1 ); }

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

недействительная  рекурсивная функция ( целое  число )  {  если  ( число  <  4 )  рекурсивная функция ( число  +  1 );  printf ( "% d \ n " ,  число ); }

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

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

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

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

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

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

• Если для некоторой константы , то${\displaystyle f(n)=O(n^{\log _{b}a-\epsilon })}$${\displaystyle \epsilon >0}$${\displaystyle T(n)=\Theta (n^{\log _{b}a})}$
• Если , то${\displaystyle f(n)=\Theta (n^{\log _{b}a})}$${\displaystyle T(n)=\Theta (n^{\log _{b}a}\log n)}$
• Если для некоторой константы , и если для некоторой константы c <1 и всех достаточно больших n , то${\displaystyle f(n)=\Omega (n^{\log _{b}a+\epsilon })}$${\displaystyle \epsilon >0}$${\displaystyle a\cdot f(n/b)\leq c\cdot f(n)}$${\displaystyle T(n)=\Theta (f(n))}$

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Бэррон, Дэвид Уильям (1968) [1967]. Написано в Кембридже, Великобритания. Гилл, Стэнли (ред.). Рекурсивные техники в программировании . Компьютерные монографии Макдональда (1-е изд.). Лондон, Великобритания: Macdonald & Co. (Publishers) Ltd. SBN 356-02201-3. (viii + 64 страницы)
• Рубио-Санчес, Мануэль (2017). Введение в рекурсивное программирование . CRC Press . 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 Press . ISBN 0-262-51087-1.
• Дейкстра, Эдсгер В. (1960). «Рекурсивное программирование». Numerische Mathematik . 2 (1): 312–318. DOI : 10.1007 / BF01386232 . S2CID  127891023 .

Внешние ссылки [ править ]