Есть ли что-то, что можно сделать с рекурсией, которая не может быть выполнена с помощью циклов?

Бывают случаи, когда использование рекурсии лучше, чем использование цикла, и времена, когда использование цикла лучше, чем использование рекурсии. При выборе «правильного» можно сохранить ресурсы и /или привести к меньшему количеству строк кода.

Есть ли случаи, когда задача может быть выполнена только с помощью рекурсии, а не цикла?

122 голоса | спросил Pikamander2 22 72015vEurope/Moscow11bEurope/MoscowSun, 22 Nov 2015 07:45:43 +0300 2015, 07:45:43

11 ответов


162

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

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

Часто рекурсивное решение проблемы более красиво. Это технический термин, и это важно.

ответил Scant Roger 22 72015vEurope/Moscow11bEurope/MoscowSun, 22 Nov 2015 09:00:00 +0300 2015, 09:00:00
75

Нет.

Приступая к основам very необходимых минимумов для вычисления, вам просто нужно быть в состоянии цикла (этого недостаточно, но является необходимым компонентом). Не важно как .

Любой язык программирования, который может реализовать машину Тьюринга, называется завершен полным завершением . И есть много языков, которые завершаются.

Мой любимый язык в том смысле, что он «работает на самом деле»? Полная полнота Тьюринга - это FRACTRAN , которая Полный комплект . Он имеет одну структуру цикла, и вы можете реализовать в ней машину Тьюринга. Таким образом, все, что можно вычислить, может быть реализовано на языке, который не имеет рекурсии. Поэтому существует nothing , что рекурсия может дать вам в терминах вычислимости, что простой цикл не может.

Это действительно сводится к нескольким пунктам:

  • Любое вычислимое вычислимо на машине Тьюринга
  • Любой язык, который может реализовать машину Тьюринга (так называемый Turing complete), может вычислять все, что любой другой язык может
  • Поскольку существуют машины Тьюринга на языках, которые не имеют рекурсии (и есть другие, у которых only есть рекурсия, когда вы попадаете в некоторые другие esolangs), обязательно верно, что нет ничего, что вы может сделать с рекурсией, что вы не можете сделать с циклом (и ничего не можете сделать с циклом, который вы не можете сделать с рекурсией).

Это не означает, что есть некоторые классы проблем, которые легче воспринимать с рекурсией, а не с циклом или с циклом, а не с рекурсией. Тем не менее, эти инструменты слишком эффективны.

И хотя я принял это к экстремальному «esolang» (в основном потому, что вы можете найти вещи, которые являются Тьюрингом, и реализованы довольно странно), это не означает, что esolangs каким-либо образом являются необязательными. Существует целый список вещей, которые случайно завершены Тьюрингом , включая Magic the Gathering, Sendmail , Шаблоны MediaWiki и система типа Scala. Многие из них далеки от оптимального, когда дело доходит до практического применения, просто чтобы вы могли вычислить все, что можно вычислить с помощью этих инструментов.


Эта эквивалентность может стать особенно интересной, когда вы попадаете в определенный тип рекурсии, известный как tail call .

Если у вас есть, скажем, факторный метод, написанный как:

 int fact(int n) {
    return fact(n, 1);
}

int fact(int n, int accum) {
    if(n == 0) { return 1; }
    if(n == 1) { return accum; }
    return fact(n-1, n * accum);
}

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

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


Если вы хотите попасть в сторону теории, см. Церковь Тестирование Тьюринга . Вы также можете найти церковное исследование на CS.SE, чтобы быть полезным.

ответил 22 72015vEurope/Moscow11bEurope/MoscowSun, 22 Nov 2015 08:11:44 +0300 2015, 08:11:44
30
  

Существуют ли случаи, когда задача может быть выполнена только с помощью рекурсии,   а не цикл?

Вы всегда можете превратить рекурсивный алгоритм в цикл, который использует структуру данных Last-In-First-Out (стек AKA) для хранения временного состояния, потому что рекурсивный вызов в точности соответствует сохранению текущего состояния в стеке, алгоритм, а затем восстановление состояния. Короткий ответ: Нет, таких случаев нет .

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

Это рекурсия, если вы сами реализуете вызов рекурсии, как отдельные шаги «push state» и «jump to begin» и «pop state»? И ответ на этот вопрос: Нет, он все еще не называется рекурсией, он называется итерацией с явным стеком (если вы хотите использовать установленную терминологию).


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

Итак, давайте рассмотрим вопрос, существуют ли общие задачи, для которых существуют только рекурсивные алгоритмы. Из комментария @WizardOfMenlo в вопросе Функция Аккермана - простой пример этого. Таким образом, концепция рекурсии стоит сама по себе, даже если ее можно реализовать с помощью другой компьютерной программы (итерация с явным стеком).

ответил hyde 22 72015vEurope/Moscow11bEurope/MoscowSun, 22 Nov 2015 16:23:58 +0300 2015, 16:23:58
20

Это зависит от того, насколько строго вы определяете «рекурсию».

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

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

 public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  if (m == 0)
    return  n+1;
  if (n == 0)
    return Ackermann(m - 1, 1);
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

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

 public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
restart:
  if (m == 0)
    return  n+1;
  if (n == 0)
  {
    m--;
    n = 1;
    goto restart;
  }
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

Затем мы очистим удаление goto, чтобы отключить велоцирапторы и оттенок Дейкстры:

 public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  while(m != 0)
  {
    if (n == 0)
    {
      m--;
      n = 1;
    }
    else
      return Ackermann(m - 1, Ackermann(m, n - 1));
  }
  return  n+1;
}

Но для удаления других рекурсивных вызовов нам нужно будет хранить значения некоторых вызовов в стеке:

 public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  Stack<BigInteger> stack = new Stack<BigInteger>();
  stack.Push(m);
  while(stack.Count != 0)
  {
    m = stack.Pop();
    if(m == 0)
      n = n + 1;
    else if(n == 0)
    {
      stack.Push(m - 1);
      n = 1;
    }
    else
    {
      stack.Push(m - 1);
      stack.Push(m);
      --n;
    }
  }
  return n;
}

Теперь, когда мы рассматриваем исходный код, мы, безусловно, превратили наш рекурсивный метод в итеративный.

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

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

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

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

ответил Jon Hanna 23 12015vEurope/Moscow11bEurope/MoscowMon, 23 Nov 2015 16:13:03 +0300 2015, 16:13:03
9

Классический ответ «нет», но позвольте мне уточнить, почему я думаю, что «да» - лучший ответ.


Прежде чем продолжить, давайте сделаем что-то в стороне: от вычислимости & Сложность:

  • Ответ «нет», если вам разрешено иметь дополнительный стек при циклировании.
  • Ответ будет «да», если вам не разрешены дополнительные данные при циклировании.

Хорошо, теперь давайте поместим одну ступню на практике, оставив другую ногу в теории земли.


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

Когда это различие имеет значение? Когда вы работаете с инструментами реального мира. Вот пример:

Предположим, вы реализуете N-way mergesort. У вас может быть цикл for, который проходит через каждый из сегментов N, называет их mergesort, а затем объединяет результаты.

Как вы можете распараллелить это с помощью OpenMP?

В рекурсивном царстве это очень просто: просто поместите #pragma omp parallel for вокруг вашего цикла, который идет от 1 до N, и все готово. В итеративном царстве вы не можете этого сделать. Вы должны запускать потоки вручную и передавать им соответствующие данные вручную, чтобы они знали, что делать.

С другой стороны, есть другие инструменты (такие как автоматические векторизаторы, например #pragma vector), которые работают с циклами, но совершенно бесполезны с рекурсией.

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

i.e .: Инструменты для одной парадигмы не переводятся автоматически в другие парадигмы.

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

ответил Mehrdad 24 22015vEurope/Moscow11bEurope/MoscowTue, 24 Nov 2015 14:05:27 +0300 2015, 14:05:27
8

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

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

Подводя итог:

  • Случай рекурсии = поток управления + стек (+ куча)
  • Случай цикла = поток управления + куча

Предполагая, что элемент control flow является достаточно мощным, единственное различие заключается в доступных типах памяти. Итак, мы остались с 4 случаями (сила выразительности указана в круглых скобках):

  1. Нет стека, без кучи: рекурсия и динамические структуры невозможны. (рекурсия = цикл)
  2. Stack, no heap: рекурсия в порядке, динамические структуры невозможны. (цикл рекурсии>)
  3. Нет стека, куча: рекурсия невозможна, динамические структуры в порядке. (рекурсия = цикл)
  4. Стек, куча: рекурсия и динамические структуры в порядке. (рекурсия = цикл)

Если правила игры немного строже, а рекурсивная реализация запрещена для использования циклов, мы получаем это вместо:

  1. Нет стека, без кучи: рекурсия и динамические структуры невозможны. (рекурсия <loop)
  2. Stack, no heap: рекурсия в порядке, динамические структуры невозможны. (цикл рекурсии>)
  3. Нет стека, куча: рекурсия невозможна, динамические структуры в порядке. (рекурсия <loop)
  4. Стек, куча: рекурсия и динамические структуры в порядке. (рекурсия = цикл)

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

ответил Alexander Kogtenkov 22 72015vEurope/Moscow11bEurope/MoscowSun, 22 Nov 2015 13:53:27 +0300 2015, 13:53:27
2

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

  • Вызывает переполнение стека.
  • Полностью запутывающие начинающие программисты.
  • Создание функций быстрого поиска, которые на самом деле являются O (n ^ n).
ответил jpa 24 22015vEurope/Moscow11bEurope/MoscowTue, 24 Nov 2015 09:09:58 +0300 2015, 09:09:58
1

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

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

ответил gnasher729 22 72015vEurope/Moscow11bEurope/MoscowSun, 22 Nov 2015 16:47:40 +0300 2015, 16:47:40
1

Если вы программируете на c ++ и используете c ++ 11, то есть одна вещь, которая должна быть выполнена с использованием рекурсий: constexpr. Но стандарт ограничивает это до 512, как описано в этом ответе . Использование циклов в этом случае невозможно, так как в этом случае функция не может быть constexpr, но это изменяется в c ++ 14.

ответил BЈовић 25 32015vEurope/Moscow11bEurope/MoscowWed, 25 Nov 2015 13:28:52 +0300 2015, 13:28:52
0
  • Если рекурсивный вызов является самым первым или последним оператором (исключая проверку условий) рекурсивной функции, его довольно легко перевести в структуру цикла.
  • Но если функция выполняет некоторые другие функции до и после рекурсивного вызова , тогда было бы громоздко преобразовать ее в циклы.
  • Если функция имеет несколько рекурсивных вызовов, преобразование ее в код, использующий только циклы, будет практически невозможным. Для того, чтобы не отставать от данных, потребуется несколько стеков. В рекурсии сам стек вызовов будет работать как стек данных.
ответил Gulshan 27 52015vEurope/Moscow11bEurope/MoscowFri, 27 Nov 2015 09:37:14 +0300 2015, 09:37:14
-6

Я согласен с другими вопросами. Вы ничего не можете сделать с рекурсией, которую вы не можете сделать с циклом.

НО , на мой взгляд рекурсия может быть очень опасной. Во-первых, для некоторых его более трудно понять, что на самом деле происходит в коде. Во-вторых, по крайней мере для C ++ (Java я не уверен) каждый шаг рекурсии влияет на память, потому что каждый вызов метода вызывает накопление памяти и инициализацию заголовка методов. Таким образом вы можете взорвать свой стек. Просто попробуйте рекурсию чисел Фибоначчи с высоким входным значением.

ответил Ben1980 22 72015vEurope/Moscow11bEurope/MoscowSun, 22 Nov 2015 12:42:27 +0300 2015, 12:42:27

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132