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

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

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

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

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

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

Нет.

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

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

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

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

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

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

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

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

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

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 полезным.

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

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

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

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

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

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

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

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

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

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;
}

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

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

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

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

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

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

Прежде чем продолжить, давайте разберемся с чем-то: с точки зрения вычислимости и сложности:

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

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

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

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

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

Как вы могли бы распараллелить это с OpenMP?

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

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

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

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

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

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

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

Обобщить:

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

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

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

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

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

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

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

• Причинение переполнения стека.
• Совершенно запутанные начинающие программисты.
• Создание быстро выглядящих функций, которые на самом деле O (n ^ n).

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

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

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

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

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

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