Какие рекурсивные функции нельзя переписать с помощью циклов?

Question

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

При каких условиях становится невозможным переписать рекурсивную функцию с использованием цикла (если такие условия существуют)?

Answer 1

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

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

Answer 2

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

Обычно хвостовую рекурсию легко преобразовать в цикл:

A(x) {
  if x<0 return 0;
  return something(x) + A(x-1)
}

Можно перевести на:

A(x) {
  temp = 0;
  for i in 0..x {
    temp = temp + something(i);
  }
  return temp;
}

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

Следующее:

treeSum(tree) {
  if tree=nil then 0
  else tree.value + treeSum(tree.left) + treeSum(tree.right);
}

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

treeSum(tree) {
  walk = tree;
  temp = 0;
  while walk != nil {
    temp = temp + walk.value + treeSum(walk.right);
    walk = walk.left;
  }
}

Answer 3

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

Просто подумайте, что делает процессор, он выполняет инструкции в одном цикле.

Answer 4

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

• обход дерева

• быстрый Фурье

• быстрые сортировки (и некоторые другие iirc)

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

Answer 5

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

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

Answer 6

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

Answer 7

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

Answer 8

В SICP авторы бросают вызов читателю, чтобы он предложил чисто итеративный метод реализации задачи «подсчета изменений» ( вот пример из Project Euler).

Но строгий ответ на ваш вопрос уже был дан - циклы и стеки могут реализовывать любую рекурсию.

Answer 9

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

Answer 10

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