Как вы можете эмулировать рекурсию со стеком?

Question

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

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

Например, предположим, у меня есть рекурсивная функция, подобная этой

function f(n, i) {
  if n <= i return n
  if n % i = 0 return f(n / i, i)
  return f(n, i + 1)
}

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

Answer 1

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

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

fib(n)
    if n < 2 return n
    return fib(n-1) + fib(n-2)

function fib(n, i)
    stack.empty()
    stack.push(<is_arg, n>)
    while (!stack.size() > 2 || stack.top().is_arg)
        <isarg, argn> = stack.pop()
        if (isarg)
            if (argn < 2)
                stack.push(<is_result, argn>)
            else
                stack.push(<is_arg, argn-1>)
                stack.push(<is_arg, argn-2>)
        else
            <isarg_prev, argn_prev> = stack.pop()
            if (isarg_prev)
                stack.push(<is_result, argn>)
                stack.push(<is_arg, argn_prev>)
            else
                stack.push(<is_result, argn+argn_prev>)
     return stack.top().argn

Объяснение:каждый раз, когда вы берете предмет из стека, вам нужно проверить, нужно ли его расширять или нет.Если это так, поместите соответствующие аргументы в стек, если нет, дайте ему слиться с предыдущими результатами.В случае Фибоначчи, когда вычисляется fib(n-2) (и он доступен в верхней части стека), извлекается n-1 (один за вершиной стека), под ним ставится результат fib(n-2), а затем fib(n-1)расширяется и вычисляется.Если два верхних элемента стека были оба результата, конечно, вы просто добавляете их и перемещаете в стек.

Если вы хотите посмотреть, как будет выглядеть ваша собственная функция, вот она:

function f(n, i)
    stack.empty()
    stack.push(n)
    stack.push(i)
    while (!stack.is_empty())
        argi = stack.pop()
        argn = stack.pop()
        if argn <= argi
            result = argn
        else if n % i = 0
            stack.push(n / i)
            stack.push(i)
        else
            stack.push(n)
            stack.push(i + 1)
    return result

Answer 2

Вы можете преобразовать свой код для использования стека следующим образом:

stack.push(n)
stack.push(i)
while(stack.notEmpty)
    i = stack.pop()
    n = stack.pop()
    if (n <= i) {
        return n
    } else if (n % i = 0) {
        stack.push(n / i) 
        stack.push(i)
    } else {
        stack.push(n) 
        stack.push(i+1)
    }
}

Примечание: я не проверял это, поэтому он может содержать ошибки, но дает вам идею.

Answer 3

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

Answer 4

И ваш пример, и функция Фибоначчи могут быть переписаны итеративно без использования стека.

Вот пример, где требуется стек, Функция Аккермана :

def ack(m, n):
    assert m >= 0 and n >= 0
    if m == 0: return n + 1
    if n == 0: return ack(m - 1, 1)
    return ack(m - 1, ack(m, n - 1))

Исключение рекурсии:

def ack_iter(m, n):
    stack = []
    push = stack.append
    pop = stack.pop
    RETURN_VALUE, CALL_FUNCTION, NESTED = -1, -2, -3

    push(m) # push function arguments
    push(n)
    push(CALL_FUNCTION) # push address
    while stack: # not empty
        address = pop()
        if address is CALL_FUNCTION:
            n = pop()  # pop function arguments
            m = pop()
            if m == 0: # return n + 1
                push(n+1) # push returned value
                push(RETURN_VALUE)
            elif n == 0: # return ack(m - 1, 1)
                push(m-1)
                push(1)
                push(CALL_FUNCTION)
            else: # begin: return ack(m - 1, ack(m, n - 1))
                push(m-1) # save local value
                push(NESTED) # save address to return
                push(m)
                push(n-1)
                push(CALL_FUNCTION)
        elif address is NESTED: # end: return ack(m - 1, ack(m, n - 1))
            # old (m - 1) is already on the stack
            push(value) # use returned value from the most recent call
            push(CALL_FUNCTION)
        elif address is RETURN_VALUE:
            value = pop() # pop returned value
        else:
            assert 0, (address, stack)
    return value

Обратите внимание, что здесь нет необходимости помещать метки CALL_FUNCTION, RETURN_VALUE и value в стек.

Пример

print(ack(2, 4)) # -> 11
print(ack_iter(2, 4))
assert all(ack(m, n) == ack_iter(m, n) for m in range(4) for n in range(6))
print(ack_iter(3, 4)) # -> 125