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

Материал из wikixw
Перейти к навигации Перейти к поиску

Эта статья посвящена рекурсивным подходам к решению задач. Доказательства с помощью рекурсии см. В разделе математическая индукция. Рекурсия в аббревиатурах компьютерных наук приведена в разделе рекурсивные аббревиатуры § примеры, связанные с компьютером.

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

   Сила рекурсии, очевидно, заключается в возможности определения бесконечного множества объектов конечным утверждением. Точно так же бесконечное число вычислений может быть описано конечной рекурсивной программой, даже если эта программа не содержит явных повторений.
   - Niklaus Wirth, Algorithms + Data Structures = Programs, 1976

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Рекурсивный тип данных

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

data ListOfStrings = EmptyList | Cons String ListOfStrings

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

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

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

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

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

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

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

Основные статьи: Коиндукция и Корекурсия

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

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

Поток строк это объект s такой что: 

голова(ы) - это струна, и
хвост(ы) - это поток струн.

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

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

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

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

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

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

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

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

Основная статья: Взаимная рекурсия

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

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

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

Основная статья: Анонимная рекурсия

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

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

См. также: Структурная рекурсия

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

   [Функции, потребляющие структурированные данные] обычно разлагают свои аргументы на непосредственные структурные компоненты и затем обрабатывают эти компоненты. Если один из непосредственных компонентов принадлежит к тому же классу данных, что и входные данные, функция рекурсивна. По этой причине мы называем эти функции (структурно) рекурсивными функциями.
   - Felleisen, Findler, Flatt, and Krishnaurthi, How to Design Programs, 2001

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

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

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

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

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

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

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

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

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

   fact ⁡ ( n ) = { 1 if  n = 0 n ⋅ fact ⁡ ( n − 1 ) if  n > 0

Псевдокод (рекурсивный): 

функция factorial is:    
input: integer n такая, что n >= 0>
output: [n × (n-1) × (n-2) × ... × 1]



 1. если n равно 0, верните 1
 2. в противном случае верните [ N × факториал(n-1) ]



 конечный факториал

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

   b n = n b n − 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

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

Псевдокод (итеративный): 

функция factorial is:

input: integer n такая, что n >= 0>

output: [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 ) = f a c t a c c ⁡ ( n , 1 ) f a c t a c c ⁡ ( n , t ) = { t if  n = 0 f a c t a c c ⁡ ( n − 1 , n t ) if  n > 0

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

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

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

   gcd ( x , y ) = { x if  y = 0 gcd ( y , remainder ⁡ ( x , y ) ) if  y > 0

Псевдокод (рекурсивный): 

функция gcd это:
входныеданные: целое число x, целое число y такое, что x > 0 и > y >= 0



1. если y равно 0, верните x
2. в противном случае верните [ gcd( y, (остаток от x/y) ) ]



конец gcd

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

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

Вычисление рекуррентного соотношения для x = 27 и y = 9: 

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

Вычисление рекуррентного соотношения для x = 111 и y = 259: 

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 is:

input: integer x, integer y такая, что x >= > y и y >= 0



1. создайте новую переменную с именем остаток



2. начать цикл
1. если y равно нулю, выходите из цикла
2. установите остаток на остаток от x / y
3. установите x в y
4. установите y в значение остаток
5. повторите цикл



3. возврат x



конец gcd

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

Ханойские башни[править]

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

Главная статья: Башни Ханоя

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

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

   hanoi ⁡ ( n ) = { 1 if  n = 1 2 ⋅ hanoi ⁡ ( n − 1 ) + 1 if  n > 1

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

   h n = 2 h n − 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, такая, что n > = > 1

1. если n равно 1, то верните 1

2. возвращение [2 * [вызов Ханоя(n-1)] + 1]

конец Ханоя

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

Явная формула для башен Ханоя: 

h1 = 1 = 21-1
h2 = 3 =2 2-1
h3 = 7 = 23-1
h4 = 15 = 24-1
h5 = 31 = 25-1
h6 = 63 = 26-1
h7 = 127 = 27-1

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

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

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

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

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

/ *
Вызовите binary_search с правильными начальными условиями.

Вход:
данные-это массив целых чисел, отсортированный в порядке возрастания,
найти это число для поиска,
count-общее количество элементов в массиве,

вывод:
результат binary_search

*/
инт поиск(инт *сведения, инт зрителями, инт граф)
{
   // начало = 0 (начальный индекс)
   // конец = количество - 1 (верхний индекс)
   вернуться binary_search(сведения, зрителями, 0, отсчет-1);
}

/*
двоичный поиск алгоритм.

Входные данные:
данные-это массив целых чисел, отсортированных в порядке возрастания,
toFind-целое число для поиска,
start-минимальный индекс массива,
end-это максимальный
выходной индекс массива:
позиция целого числа toFind в данных массива,
-1, если не найдено
*/
int binary_search(int *data, int toFind, int start, int end)
{
   //Get the midpoint.
   int mid = start + (end - start)/2;   //целочисленное деление

   / / условие остановки.
   if (start >> end)
      return -1;
   else if (data[mid] == toFind)        / / найдено?
      возвращение середине;
   иначе если (данные[средний] > найти)         //данных больше, чем найти, поиск нижней половине
      вернуться binary_search(сведения, найти, начало, середина-1);
   иначе                                 //данных меньше найти, поиск верхней половине
      вернуться binary_search(сведения, найти, СЧ+1, конца);
}

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

Основная статья: Рекурсивный тип данных

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

   "Рекурсивные алгоритмы особенно уместны, когда основная проблема или данные, подлежащие обработке, определены в рекурсивных терминах."

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

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

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

Основная статья: Связанный список

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

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

Поскольку структура данных узла struct определена рекурсивно, процедуры, которые работают с ней, могут быть реализованы естественным образом как рекурсивные процедуры. Процедура 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;  / / указатель на правое поддерево
};

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

// Test if tree_node contains i; return 1 if so, 0 if not.
инт tree_contains(структура узла *tree_node, инт я) {
   если (tree_node == значение null)
       возвращает 0;  // базовый случай
   еще если (tree_node->данные == я,)
       возврат 1;
   еще
       вернуться tree_contains(tree_node->слева, я) || tree_contains(tree_node->право, я);
}

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

// Inorder traversal:
void tree_print(struct node *tree_node) {
       if (tree_node != NULL) {                  //base case
               tree_print(tree_node- > >left);      / / go left
               printf("%d", tree_node- > >data);   / / print the integer followed by a space
               tree_print(tree_node->>right);     // go right
       }
}

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

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

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

import java.io.*;

public class FileSystem {

public static void main (String [] args) { traverse (); }

/** * Obtains the filesystem roots * Proceeds with the recursive filesystem traversal */ 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 "является косвенным, который вызывает"rtraverse". Этот пример не нуждается в" базовом случае " сценария из-за того, что всегда будет некоторое фиксированное количество файлов или каталогов в данной файловой системе.

Вопросы реализации[править]

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

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

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

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

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

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

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

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

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

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

Глубина-первый поиск[править]

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

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

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

При коротком замыкании это происходит вместо того, чтобы:

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

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

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

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

боол tree_contains(структура узла *tree_node, инт я) {
   если (tree_node == значение null)
       возвращает значение false;  // базовый случай
   еще если (tree_node->данные == я,)
       возврат истина;
   иначе
       возврат tree_contains(tree_node->слева, я) ||
              tree_contains(tree_node->право, я);
}

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

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

// предполагает tree_node != Значение null
типа bool tree_contains_do(структура узла *tree_node, инт я) {
   если (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) избазы x: 

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

и 

функция итеративная(n)
x = Xбаза
для i = основание+1 к n
x = f (i, x)
возврат x

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

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

unsigned int factorial(unsigned int n) {
 unsigned int product = 1; / / пустой продукт равен 1
 while (n) {
   product *= n;
   --n;
 }
 return product;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В простом случае функции, вызывающей саму себя только один раз, инструкции, помещенные перед рекурсивным вызовом, выполняются один раз за рекурсию перед любой из инструкций, помещенных после рекурсивного вызова. Последние выполняются повторно после достижения максимальной рекурсии. Рассмотрим этот пример: Функция 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);
}

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

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

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

Основная статья: Главная теорема (анализ алгоритмов)

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

T ( n ) = a ⋅ T ( n / b ) + f ( n )

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

   Если f ( n ) = O ( n log b ⁡ a − ϵ )для некоторой константы ϵ > 0 
   Если f ( n ) = Θ ( n log b ⁡ a ) 
   Если f ( n ) = Ω ( n log b ⁡ a + ϵ ) для некоторой константы ϵ > 0  \Эпсилон >0и если a ⋅ f ( n / b ) ≤ c ⋅ f ( n ) для некоторой константы c < 1 и всех достаточно больших n, то T ( n ) = Θ ( f ( n ) )

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

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

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

Barron, David William (1968) [1967]. Написано в Кембридже, Великобритания. Джилл, Стэнли (ред.). Рекурсивные методы в программировании. Компьютерные монографии Макдональда (1 изд.). Лондон, Великобритания: Macdonald & Co. (Publishers) Ltd.

Rohl, Jeffrey S. (1984). Рекурсия Через Паскаль. Издательство Кембриджского Университета.

  • Хелман, Пол; Верофф, Роберт. Стены и зеркала.
  • Абельсон, Гарольд; Сассман, Джеральд Джей; Сассман, Джули (1996). Структура и интерпретация компьютерных программ (2-е изд.). MIT Press. ISBN 0-262-51087-1.

Dijkstra, Edsger W. (1960). "Рекурсивное Программирование". Numerische Mathematik. 2

Пруф[править]

/users.cs.duke.edu/~ola/ap/recurrence.html

Источник — https://wikixw.ru/index.php?title=Рекурсия_(информатика)&oldid=22637