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

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

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

Сила рекурсии, очевидно, заключается в возможности определить бесконечное множество объектов с помощью конечного утверждения. Точно так же бесконечное число вычислений может быть описано конечной рекурсивной программой, даже если эта программа не содержит явных повторений.
- Никлаус Вирт , Алгоритмы + Структуры данных = Программы , 1976 г. ^[4]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поток строк — это такой объект, что:
  head(s) — это строка, а
  хвост(ы) — это поток строк.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Многие известные рекурсивные алгоритмы генерируют совершенно новый фрагмент данных из имеющихся данных и повторяются на нем. HtDP ( «Как разрабатывать программы ») называет этот вид генеративной рекурсией. Примеры генеративной рекурсии включают: gcd , быструю сортировку , двоичный поиск , сортировку слиянием , метод Ньютона , фракталы и адаптивное интегрирование .
— Маттиас Феллейзен, Продвинутое функциональное программирование , 2002 г. ^[7]

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

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

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

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

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

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

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

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

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

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

Факториал: обычное и короткое замыкание

Обычная рекурсия

Короткая рекурсия

int   fac1  (  intn   )  )   { 
    if   (  n   <   0  = 
       вернуть   1  ; 
     иначе 
       верните   fac1  (  n  -1  )  *  n  ; 
  } }

int   fac2  (  int   n  )   { 
    // Assert(n >= 2); 
     если   (  n   ==   2  ) 
       вернуть   2  ; 
     иначе 
       верните   fac2  (  n  -1  )  *  n  ; 
  } 
 int   fac2wrapper  (  int   n  )   { 
    if   (  n   <=   1  ) 
       return   1  ; 
     иначе 
       верните   fac2  (  n  ); 
  }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекурсивные алгоритмы можно заменить нерекурсивными аналогами. ^[18] Одним из методов замены рекурсивных алгоритмов является их моделирование с использованием динамической памяти вместо стековой памяти . ^[19] Альтернативой является разработка алгоритма замены, полностью основанного на нерекурсивных методах, что может оказаться сложной задачей. ^[20] Например, рекурсивные алгоритмы сопоставления подстановочных знаков , такие как алгоритм Рича Зальца подстановочный , ^[21]когда-то были типичными. Нерекурсивные алгоритмы для той же цели, такие как алгоритм сопоставления подстановочных знаков Краусса , были разработаны, чтобы избежать недостатков рекурсии. ^[22] и улучшались лишь постепенно на основе таких методов, как сбор тестов и профилирование производительности. ^[23]

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

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

Хвостовая рекурсия :

Усиление рекурсии:

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

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

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

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

Рассмотрим эти две функции:

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

void   recursiveFunction  (  int   num  )   { 
     printf  (  "%d  \n  "  ,   num  ); 
      если   (  число   <   4  ) 
         recursiveFunction  (  число   +   1  ); 
  }

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

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

Выходные данные функции 2 аналогичны выходным данным функции 1 с поменянными местами строками.

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

Также обратите внимание, что порядок операторов печати обратный, что связано с тем, как функции и операторы хранятся в стеке вызовов .

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

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

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

\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) ] 
 

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

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

b_{n}=nb_{n-1}

b_{0}=1

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

Вычисление рекуррентного соотношения для n = 4:

б ₄ = 4 × б ₃
               знак равно 4 × (3 × б ₂ ) 
               знак равно 4 × (3 × (2 × б ₁ )) 
               = 4 × (3 × (2 × (1 × б ₀ ))) 
               = 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.  начать  цикл 
            1. если  n  равно 0,  выйти из  цикла 
            2.  установите   Running_total  равным (  Running_total  ×  n  ) 
            3.  уменьшить   n 
            4.  Повторить  цикл 
 

    3.  вернуть   текущий_общий 


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

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

{\begin{aligned}\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{aligned}}

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

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

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

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

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

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

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

конец  НОД

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

\gcd(x,y)=\gcd(y,x\%y)

если

y\neq 0

\gcd(x,0)=x

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

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

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

функция  НОД: 

ввод  : целое число  x  , целое число  y  такое, что  x  >=  y  и  y  >= 0
 

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

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

    3.  вернуть   х 


конец  НОД

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

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

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

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

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

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

h_{n}=2h_{n-1}+1

h_{1}=1

Вычисление рекуррентного соотношения для n = 4:
ханой(4) = 2×ханой(3) + 1 = 2×(2×ханой(2) + 1) + 1 = 2×(2×(2×Ханой(1) + 1) + 1) + 1 = 2×(2×(2×1 + 1) + 1) + 1 = 2×(2×(3) + 1) + 1 = 2×(7) + 1 = 15

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

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

функция  Ханой: 

ввод  : целое число  n  , такое что  n  >=  1 


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

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

чем  Ханой

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

Явная формула для Ханойских башен:

час ₁ = 1 = 2 ¹- 1 
  час ₂ = 3 = 2 ²- 1 
  х3 ₌ 7 = 2 ³- 1 
  ч ₄ = 15 = 2 ⁴- 1 
  ч ₅ = 31 = 2 ⁵- первый 
  ч ₆ = 63 = 2 ⁶ - 1
h ₇ = 127 = 2 ⁷ - 1

В общем: 
  = _{час п} 2 ^н - 1, для всех n >= 1

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

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

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

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

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

  ВВОД: 
 данные — это массив целых чисел, отсортированных по возрастанию, 
 toFind — целое число для поиска, 
 count — общее количество элементов в массиве. 

 ВЫХОД: 
 результат поискаbinary_search 

 / 
  int   *  (  int   *  data  ,   int   toFind  ,   int   count  ) 
  { 
     начальный индекс) 
     // Конец = счетчик - 1 (верхний индекс) 
     returnbinary_search   // Начало = 0 (  (  data  ,   toFind  ,   0  ,   count  -1  ); 
   } 

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

  ВВОД: 
 данные представляют собой массив целых чисел, отсортированных по возрастанию, 
 toFind — целое число для поиска, 
 начало — минимальный индекс массива, 
 конец — максимальный индекс массива 
 . ВЫХОД: 
 позиция целого числа, которое нужно найти в данных массива, 
 -1, если не найдено 
 */ 
  intbinary_search   (  ,  int   *  data  start   int   toFind  ,   int   end  ,   int   )  { 
  // 
     Получаем среднюю точку. 
      int   Mid   =   начало   +   (  конец   -   начало  )  /  2  ;      //Целочисленное деление 


     if   (  start   >   end  )                       //Условие остановки (базовый случай) 
        return   -1  ; 
      else   if   (  data  [  mid  ]   ==   toFind  )          //Найдено, возвращаем индекс 
        return   Mid  ; 
      else   if   (  data  [  mid  ]   >   toFind  )           //Данные больше, чем toFind, ищем нижнюю половину 
       вернуть   двоичный_поиск  (  данные  ,   toFind  ,   начало  ,   середина  -1  ); 
      else                                   //Данные меньше, чем toFind, поиск в верхней половине 
        (   returnbinary_search  data  ,  toFind   ,  middle   +  1  ,  end   )  ; 
   }

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

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

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

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

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

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

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

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

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

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

Бинарные деревья [ править ]

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

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

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

// Проверяем, содержит ли Tree_node i;   верните 1, если да, 0, если нет. 
  inttree_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  ->  вправо  ,   я  ); 
  }

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

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

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

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

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

импортировать   java.io.File  ; 

  общественный   класс   FileSystem   { 

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

	 /** 
 * Получает корни файловой системы 
 * Приступает к рекурсивному обходу файловой системы 
 */ 
	 Private   static   void   traverse  ()   { 
		 File  []   fs   =   File  .   списокКорни  (); 
		  for   (  int   я   знак равно   0  ;   я   <   fs  .  length  ;   я  ++  )   { 
			 System  .   вне  .   println  (  фс  [  я  ]  ); 
			  if   (  fs  [  i  ]  .  isDirectory  ()   &&   fs  [  i  ]  .  canRead  ())   { 
				 rtraverse  (  fs  [  i  ]  ); 
			  } 
		 } 
	 } 

	 /** 
 * Рекурсивный обход заданного каталога 
 * 
 * @param fd указывает начальную точку обхода 
 */ 
	 Private   static   void   rtraverse  (  File   fd  )   { 
		 File  []   fss   =   fd  .   СписокФайлов  (); 

		  for   (  int   я   знак равно   0  ;   я   <   fss  .  length  ;   я  ++  )   { 
			 System  .   вне  .   println  (  фсс  [  я  ]  ); 
			  if   (  fss  [  i  ]  .  isDirectory  ()   &&   fss  [  i  ]  .  canRead  ())   { 
				 rtraverse  (  fss  [  i  ]  ); 
			  } 
		 } 
	 } 

 }

Этот код является одновременно рекурсией и итерацией — файлы и каталоги повторяются, и каждый каталог открывается рекурсивно.

Метод «rtraverse» является примером прямой рекурсии, а метод «traverse» — это функция-обертка.

«Базовый сценарий» заключается в том, что в данной файловой системе всегда будет фиксированное количество файлов и/или каталогов.

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

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

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

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

T(n)=a\cdot T(n/b)+f(n)

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

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

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

логическом программировании Рекурсия в

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

путь  (  X  ,  Y  )   :-   дуга  (  X  ,  Y  ). 
  путь  (  X  ,  Y  )   : —   дуга  (  X  ,  Z  ),   путь  (  Z  ,  Y  ).

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

Однако при логическом чтении логических программ предложения понимаются декларативно как универсально квантифицированные условные выражения. Например, рекурсивное предложение процедуры поиска пути понимается как представление знания о том, что для каждых X , Y и Z , если существует дуга от X до Z и путь от Z до Y , то существует путь от Х до Y. от В символической форме:

\forall X,Y,Z(arc(X,Z)\land path(Z,Y)\rightarrow path(X,Y)).

Логическое прочтение освобождает читателя от необходимости знать, как это предложение используется для решения проблем. Это предложение можно использовать сверху вниз, как в Прологе, чтобы свести проблемы к подзадачам. Или его можно использовать снизу вверх (или вперед ), как в Datalog , для получения выводов на основе условий. Такое разделение задач является формой абстракции , которая отделяет декларативные знания от методов решения проблем (см. Алгоритм#Алгоритм = Логика + Управление ). ^[28]

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

Примечания [ править ]

^ Грэм, Рональд; Кнут, Дональд; Паташник, Орен (1990). «1: Повторяющиеся проблемы» . Конкретная математика . Аддисон-Уэсли. ISBN 0-201-55802-5 .
^ Кухейл, Массачусетс; Негрейрос, Дж.; Сеффа, А. (2021). «Обучение рекурсивному мышлению с использованием отключенных действий» (PDF) . Мировые сделки по инженерному и технологическому образованию . 19 : 169–175.
^ Эпп, Сюзанна (1995). Дискретная математика с приложениями (2-е изд.). Издательская компания ПВС. п. 427 . ISBN 978-0-53494446-9 .
^ Вирт, Никлаус (1976). Алгоритмы + Структуры данных = Программы . Прентис-Холл . п. 126 . ISBN 978-0-13022418-7 .
^ «Функциональное программирование | Clojure для смелых и истинных» . www.braveclojure.com . Проверено 21 октября 2020 г.
^ Феллизен и др. 2001 г. , арт V «Генеративная рекурсия»
^ Перейти обратно: ^а ^б Феллейзен, Матиас (2002). «Разработка интерактивных веб-программ» . В Жеринге, Йохан (ред.). Продвинутое функциональное программирование: 4-я международная школа (PDF) . Спрингер. п. 108. ИСБН 9783540448334 .
^ Монган, Джон; Жигер, Эрик; Киндлер, Ной (2013). Разоблачение собеседований по программированию: секреты получения следующей работы (3-е изд.). Уайли . п. 115 . ISBN 978-1-118-26136-1 .
^ Хетланд, Магнус Ли (2010), Алгоритмы Python: освоение базовых алгоритмов языка Python , Apress, стр. 79, ISBN 9781430232384 .
^ Дроздек, Адам (2012), Структуры данных и алгоритмы в C++ (4-е изд.), Cengage Learning, стр. 197, ISBN 9781285415017 .
^ Дрожь, Олин. «Анатомия цикла — история масштаба и контроля» (PDF) . Технологический институт Джорджии . Проверено 3 сентября 2012 г.
^ Лямбда Ultimate. «Анатомия петли» . Лямбда Ultimate . Проверено 3 сентября 2012 г.
^ «27.1.sys — Системные параметры и функции — Документация Python v2.7.3» . Docs.python.org . Проверено 3 сентября 2012 г.
^ Краусс, Кирк Дж. (2014). «Сопоставление подстановочных знаков: эмпирический способ приручить алгоритм» . Журнал доктора Добба .
^ Мюллер, Оливер (2012). «Анатомия атаки на разрушение стека и как GCC ее предотвращает» . Журнал доктора Добба .
^ «Класс StackOverflowException» . Библиотека классов .NET Framework . Сеть разработчиков Microsoft . 2018.
^ «Поиск в глубину (DFS): итеративная и рекурсивная реализация» . Технический восторг. 2018.
^ Митрович, Иван. «Замените рекурсию итерацией» . МысльВоркс .
^ Ла, Ун Гю (2015). «Как заменить рекурсивные функции с помощью стека и цикла while, чтобы избежать переполнения стека» . КодПроект.
^ Мертель, Том (2013). «Профессиональные хитрости: рекурсия к итерации, часть 2: устранение рекурсии с помощью секретного трюка с путешествием во времени» .
^ Зальц, Рич (1991). "wildmat.c" . Гитхаб .
^ Краусс, Кирк Дж. (2008). «Сопоставление подстановочных знаков: алгоритм» . Журнал доктора Добба .
^ Краусс, Кирк Дж. (2018). «Сопоставление подстановочных знаков: улучшенный алгоритм для больших данных» . Развивайтесь ради производительности.
^ Грэм, Кнут и Паташник 1990 , §1.1: Ханойская башня
^ Эпп 1995 , стр. 427–430: Ханойская башня.
^ Epp 1995 , стр. 447–448: Явная формула для последовательности Ханойской башни.
^ Вирт 1976 , с. 127
^ Рассел, Стюарт Дж .; Норвиг, Питер. (2021). Искусственный интеллект: современный подход §9.3, §9.4 (4-е изд.). Хобокен: Пирсон. ISBN 978-0134610993 . LCCN 20190474 .

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

Бэррон, Дэвид Уильям (1968) [1967]. Написано в Кембридже, Великобритания. Гилл, Стэнли (ред.). Рекурсивные методы в программировании . Компьютерные монографии Макдональда (1-е изд.). Лондон, Великобритания: Macdonald & Co. (Publishers) Ltd. SBN. 356-02201-3 . (viii+64 страницы)
Феллейзен, Матиас; Финдлер, Роберт Б.; Флэтт, Мэтью; Кришнамурти, Шрирам (2001). Как разрабатывать программы: введение в вычислительную технику и программирование . МТИ Пресс . ISBN 0262062186 .
Рубио-Санчес, Мануэль (2017). Введение в рекурсивное программирование . ЦРК Пресс . 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 .
Helman, Paul; Veroff, Robert. Walls and Mirrors.
Abelson, Harold; Sussman, Gerald Jay; Sussman, Julie (1996). Structure and Interpretation of Computer Programs (2nd ed.). MIT Press. ISBN 0-262-51087-1.
Dijkstra, Edsger W. (1960). "Recursive Programming". Numerische Mathematik. 2 (1): 312–318. doi:10.1007/BF01386232. S2CID 127891023.

[1] Грэм, Рональд; Кнут, Дональд; Паташник, Орен (1990). «1: Повторяющиеся проблемы» . Конкретная математика . Аддисон-Уэсли. ISBN 0-201-55802-5 .

[2] Кухейл, Массачусетс; Негрейрос, Дж.; Сеффа, А. (2021). «Обучение рекурсивному мышлению с использованием отключенных действий» (PDF) . Мировые сделки по инженерному и технологическому образованию . 19 : 169–175.

[3] Эпп, Сюзанна (1995). Дискретная математика с приложениями (2-е изд.). Издательская компания ПВС. п. 427 . ISBN 978-0-53494446-9 .

[4] Вирт, Никлаус (1976). Алгоритмы + Структуры данных = Программы . Прентис-Холл . п. 126 . ISBN 978-0-13022418-7 .

[5] «Функциональное программирование | Clojure для смелых и истинных» . www.braveclojure.com . Проверено 21 октября 2020 г.

[Felleisen_HtDP_2001-6] Феллизен и др. 2001 г. , арт V «Генеративная рекурсия»

[Felleisen_2002_108-7] Перейти обратно: ^а ^б Феллейзен, Матиас (2002). «Разработка интерактивных веб-программ» . В Жеринге, Йохан (ред.). Продвинутое функциональное программирование: 4-я международная школа (PDF) . Спрингер. п. 108. ИСБН 9783540448334 .

[8] Монган, Джон; Жигер, Эрик; Киндлер, Ной (2013). Разоблачение собеседований по программированию: секреты получения следующей работы (3-е изд.). Уайли . п. 115 . ISBN 978-1-118-26136-1 .

[9] Хетланд, Магнус Ли (2010), Алгоритмы Python: освоение базовых алгоритмов языка Python , Apress, стр. 79, ISBN 9781430232384 .

[10] Дроздек, Адам (2012), Структуры данных и алгоритмы в C++ (4-е изд.), Cengage Learning, стр. 197, ISBN 9781285415017 .

[11] Дрожь, Олин. «Анатомия цикла — история масштаба и контроля» (PDF) . Технологический институт Джорджии . Проверено 3 сентября 2012 г.

[12] Лямбда Ultimate. «Анатомия петли» . Лямбда Ultimate . Проверено 3 сентября 2012 г.

[13] «27.1.sys — Системные параметры и функции — Документация Python v2.7.3» . Docs.python.org . Проверено 3 сентября 2012 г.

[14] Краусс, Кирк Дж. (2014). «Сопоставление подстановочных знаков: эмпирический способ приручить алгоритм» . Журнал доктора Добба .

[15] Мюллер, Оливер (2012). «Анатомия атаки на разрушение стека и как GCC ее предотвращает» . Журнал доктора Добба .

[16] «Класс StackOverflowException» . Библиотека классов .NET Framework . Сеть разработчиков Microsoft . 2018.

[17] «Поиск в глубину (DFS): итеративная и рекурсивная реализация» . Технический восторг. 2018.

[18] Митрович, Иван. «Замените рекурсию итерацией» . МысльВоркс .

[19] Ла, Ун Гю (2015). «Как заменить рекурсивные функции с помощью стека и цикла while, чтобы избежать переполнения стека» . КодПроект.

[20] Мертель, Том (2013). «Профессиональные хитрости: рекурсия к итерации, часть 2: устранение рекурсии с помощью секретного трюка с путешествием во времени» .

[21] Зальц, Рич (1991). "wildmat.c" . Гитхаб .

[22] Краусс, Кирк Дж. (2008). «Сопоставление подстановочных знаков: алгоритм» . Журнал доктора Добба .

[23] Краусс, Кирк Дж. (2018). «Сопоставление подстановочных знаков: улучшенный алгоритм для больших данных» . Развивайтесь ради производительности.

[24] Грэм, Кнут и Паташник 1990 , §1.1: Ханойская башня

[25] Эпп 1995 , стр. 427–430: Ханойская башня.

[26] Epp 1995 , стр. 447–448: Явная формула для последовательности Ханойской башни.

[27] Вирт 1976 , с. 127

[28] Рассел, Стюарт Дж .; Норвиг, Питер. (2021). Искусственный интеллект: современный подход §9.3, §9.4 (4-е изд.). Хобокен: Пирсон. ISBN 978-0134610993 . LCCN 20190474 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

v t e Data structures and algorithms
Data structures	Array Associative array Binary search tree Fenwick tree Graph Hash table Heap Linked list Queue Segment tree Stack String Tree Trie
Algorithms	Backtracking Binary search Breadth-first search Brute-force search Depth-first search Divide and conquer Dynamic programming Graph traversal Fold Greedy Hash function Minimax Online Randomized Recursion Root-finding Sorting Streaming Sweep line String-searching Topological sorting
List of data structures List of algorithms

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Бинарные деревья [ править ]

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

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

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

логическом программировании Рекурсия в

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

Примечания [ править ]

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

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

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