Существует ли проблема, которая имеет только рекурсивное решение? [дубликат]

Замените вызовы функций на отправку аргументов в стек и возвращайтесь с извлечением из стека, и вы устранили рекурсию.

Редактировать: в ответ на «использование стека» не снижает затраты на пространство »

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

факториал:

def fact_rec(n):
    ' Textbook Factorial function '
    if n < 2:  return 1
    else:      return n * f(n-1)


def f(n, product=1):
    ' Tail-recursive factorial function '
    if n < 2: return product
    else:     return f(n-1, product*n)

def f(n):
    ' explicit stack -- otherwise same as tail-recursive function '
    stack, product = [n], 1
    while len(stack):
        n = stack.pop()
        if n < 2: pass 
        else:
            stack.append(n-1)
            product *= n
    return product

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

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

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

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

Все сводится к тому, сколько строк кода потребуется для решения проблемы ...

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

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

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

РЕДАКТИРОВАТЬ: Как указывали другие, существует много функций, определение которых рекурсивно - например, функция Аккермана . Однако это не означает, что они не могут быть вычислены с использованием итерационных конструкций - при условии, что у вас есть полный набор операций Тьюринга и неограниченная память.

Нет. Рекурсия - это не что иное, как стек, и вы можете достичь тех же результатов, явно реализовав стек.

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

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

на моей платформе (Python 3.1rc2 / Vista32) итеративная версия вычисляет ack (3,7) = 1021 нормально, тогда как рекурсивная версия переполняет стек. NB: это не stackoverflow на python 2.6.2 / Vista64 на другом компьютере, поэтому он, кажется, скорее зависит от платформы,

(Вики Сообщества, потому что это действительно комментарий к другому ответу [если только комментарии поддерживают код форматирование ....])

def ack(m,n):
  s = [m]
  while len(s):
     m = s.pop()
     if m == 0:
        n += 1 
     elif n == 0:
        s.append(m-1)
        n = 1
     else:
        s.append(m-1)
        s.append(m)
        n -= 1
  return n