Есть ли проблема, которая имеет только рекурсивное решение?

Ответ 1

функция Ackermann не может быть выражена без рекурсии

Ответ 2

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

Изменить: в ответ на "использование стека не уменьшает пространственные затраты"

Если рекурсивный алгоритм может работать в постоянном пространстве, он может быть записан хвостовым рекурсивным образом. если он написан в хвостовом рекурсивном формате, то любой достойный компилятор может свернуть стек. Однако это означает, что метод "convert function calls to explicit stack-push" также принимает и постоянное пространство. В качестве примера давайте возьмем факториал.

факториала:

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() следует за стеком .append() в цикле, в стеке не более одного элемента в нем, и поэтому он удовлетворяет требованиям к постоянному пространству. если вы предполагаете использовать временную переменную вместо стека с длиной 1 строки, она станет вашим стандартным итеративно-факториальным алгоритмом.

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

Ответ 3

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

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

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

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

Ответ 4

Вы можете определить Turing Machine без рекурсии (правильно?). Таким образом, для языка не требуется рекурсия Turing-complete.

Ответ 5

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

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

EDIT: Как указывали другие, существует много функций, определение которых рекурсивно - ex. функция Ackermann. Однако это не означает, что они не могут быть вычислены с использованием итеративных конструкций - пока у вас есть полный набор функций turing и неограниченная память.

Ответ 6

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

Ответ 7

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

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

Ответ 8

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

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

Я помещаю там "традиционный", потому что они действительно означают циклы, которые повторяются определенное количество раз, в то время как циклы C для (...;...;...) циклов - это маскировка петель.