Преобразование функции с двумя последовательными "хвостовыми" рекурсивными вызовами в итеративную функцию - PullRequest
Новая
       10

Преобразование функции с двумя последовательными "хвостовыми" рекурсивными вызовами в итеративную функцию

0 голосов
/ 15 мая 2018

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

Вот пример того, что я имею в виду в Python: 

def doit(x, y, L):
  if x < y:
    x += 1
  else:
    x -= 1
    y -= 1
  if y > 0:
    L.append(x)
    doit(x, y, L)
    doit(x - 1, y - 1, L)

#usage
L = []
doit(3, 5, L)
print(L)

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

1 Ответ

0 голосов
/ 15 мая 2018

Нет, для этого нет общего и простого метода, как для хвостовой рекурсивной задачи. Это верно, даже если у вас есть 1 рекурсивный вызов в конце, но функция не является хвостовой рекурсивной (например, return 5+foo(x)). Вам придется явно поддерживать стек, и тогда он будет работать даже для случаев с более чем двумя рекурсивными вызовами в конце.

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

Так что для нормальных рекурсивных функций без гарантии "max 1 version" объявите стек перед основным циклом. Каждый элемент в нем будет кортежем всех параметров. Внутри цикла получите последний элемент стека (и удалите его из стека). Затем просто скопируйте / вставьте ваше тело функции внутри цикла. Однако, кроме следующего рекурсивного вызова, создайте элемент, содержащий все значения параметров этого вызова, и поместите его в стек. Ваш код изменен: 

A = [] #your initial 'L'
stack = [(2,4,A)] #push values of initial call
while stack:
    x,y,L = stack.pop()
    print(x,y)
    if x < y:
        x += 1
    else:
        x -= 1
        y -= 1
    if y > 0:
        L.append(x)
        stack.append((x, y, L))
        stack.append((x - 1, y - 1, L))

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

...