Рекурсия Фибоначчи со стеком

Question

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

algorithm Fibonacci(x):
  i = 0
  i += Fibonacci(x-1)
  i += Fibonacci(x-2)
  return i

(Да, я знаю, что я не поставил базовый случай, и что рекурсия для фибоначчи действительно неэффективна)

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

Answer 1

в псевдо-питоне

def fib(x):
  tot = 0
  stack = [x]
  while stack:
     a = stack.pop()
     if a in [0,1]:
        tot += 1
     else:
         stack.push(a - 1)
         stack.push(a - 2)
   return tot

Если вам не нужен внешний счетчик, вам нужно будет нажать кортежи, которые отслеживают накопленную сумму, и было ли это a - 1 или a - 2.

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

Редактировать:

Давайте проанализируем выполнение следующего алгоритма Фибоначчи

def fib(x):
    if (x == 0) or (x == 1):
       return 1
    else:
        temp1 = fib(x - 1)
        temp2 = fib(x - 2)
        return temp1 + temp2

(Да, я знаю, что это даже неэффективная реализация неэффективного алгоритма, я объявил больше временных значений, чем необходимо.)

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

1. Где вернуть результат.
2. Пробел для локальных переменных.

В нашем случае у нас есть три возможных места для возврата.

1. Некоторые внешние абоненты
2. Назначить для temp1
3. Назначить для temp2

нам также нужно место для трех локальных переменных x, temp1 и temp2.давайте рассмотрим fib (3)

, когда мы первоначально вызываем fib, мы сообщаем стеку, что мы хотим вернуться туда, откуда мы делаем кулачки, x = 3, а temp1 и temp2 неинициализированы.

Затем мы помещаем в стек, который мы хотим назначить, temp1, x = 2, а temp1 и temp2 неинициализированы.Мы снова вызываем, и у нас есть стек

(assign temp1, x = 1, -, -)
(assign temp1, x = 2, -, -)
(out         , x = 3, -, -)

, теперь мы возвращаем 1 и делаем второй вызов и получаем

(assign temp2, x = 0, -, -)
(assign temp1, x = 2, temp1 = 1, -)
(out         , x = 3, -, -)

, теперь он снова возвращает 1

(assign temp1, x = 2, temp1 = 1, temp2 = 1)
(out         , x = 3, -, -)

так что это возвращает 2, и мы получаем

(out         , x = 3, temp1 =2, -)

Итак, теперь мы вернемся к

(assign temp2, x = 1, -, -)
(out         , x = 3, temp1 =2, -)

, из которого мы можем видеть наш выход.

Answer 2

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

Это явное моделирование выполнения рекурсивной реализации функции Фибоначчи.Язык C #.Для аргумента 0 функция возвращает 0 - в соответствии с определением последовательности Фибоначчи, данным Рональдом Грэмом, Дональдом Кнутом и Ореном Паташником в «Конкретной математике».Это определено также в Википедии.Проверки на наличие отрицательных аргументов опускаются.

Обычно адрес возврата хранится в стеке, а выполнение просто переходит на правильный адрес.Чтобы смоделировать это, я использовал enum

enum JumpAddress
{
    beforeTheFirstRecursiveInvocation,
    betweenRecursiveInvocations,
    afterTheSecondRecursiveInvocation,
    outsideFibFunction
}

и небольшой конечный автомат.

Кадр, хранящийся в стеке, определяется следующим образом:

class Frame
{
    public int argument;
    public int localVariable;
    public JumpAddress returnAddress;
    public Frame(int argument, JumpAddress returnAddress)
    {
        this.argument = argument;
        this.localVariable = 0;
        this.returnAddress = returnAddress;
    }
}

Это класс C # - ссылочный тип.Стек хранит ссылки на объекты, помещенные в кучу, поэтому, когда я делаю это:

Frame top = stack.Peek();
top.localVariable = lastresult;

Я изменяю объект, на который все еще ссылается ссылка на вершине стека, а не копия.

Я моделирую вызов функции, помещая кадр в стек и устанавливая адрес выполнения в моем автомате состояний в начало - beforeTheFirstRecursiveInvocation.

Для возврата из функции Iустановите переменную lastresult, переменную pointOfExecution на адрес возврата, сохраненный в верхнем фрейме, и извлеките фрейм из стека.

Вот код.

public static int fib(int n)
{
    Stack<Frame> stack = new Stack<Frame>(n);
    //Constructor uses the parameter to reserve space.
    int lastresult = 0; 
    //variable holding the result of the last "recursive" invocation            
    stack.Push(new Frame(n, JumpAddress.outsideFibFunction));
    JumpAddress pointOfExecution = JumpAddress.beforeTheFirstRecursiveInvocation;
    // that's how I model function invocation. I push a frame on the stack and set
    // pointOfExecution. Above the frame stores the argument n and a return address
    // - outsideFibFunction

    while(pointOfExecution != JumpAddress.outsideFibFunction)
    {
        Frame top = stack.Peek();
        switch(pointOfExecution)
        {
            case JumpAddress.beforeTheFirstRecursiveInvocation:
                if(top.argument <= 1)
                {
                    lastresult = top.argument;
                    pointOfExecution = top.returnAddress;
                    stack.Pop();
                }
                else
                {
                    stack.Push(new Frame(top.argument - 1, JumpAddress.betweenRecursiveInvocations));
                    pointOfExecution = JumpAddress.beforeTheFirstRecursiveInvocation;
                }
                break;
            case JumpAddress.betweenRecursiveInvocations:
                top.localVariable = lastresult;
                stack.Push(new Frame(top.argument - 2, JumpAddress.afterTheSecondRecursiveInvocation));
                pointOfExecution = JumpAddress.beforeTheFirstRecursiveInvocation;
                break;
            case JumpAddress.afterTheSecondRecursiveInvocation:
                lastresult += top.localVariable;
                pointOfExecution = top.returnAddress;
                stack.Pop();
                break;
            default:
                System.Diagnostics.Debug.Assert(false,"This point should never be reached");
                break;
        }
    }
    return lastresult;
}

Answer 3

// 0<x<100
int fib[100];
fib[1]=1;
fib[2]=1;
if(x<=2)
cout<<1;
else{
for(i=3;i<=x;i++)
   fib[i]=fib[i-1]+fib[i-2];
cout<<fib[x];
}

ИЛИ без использования вектора

   int x,y,z;
   x=1;y=1;z=1;
   if(x<=2)
    cout<<1;
   else{
   for(i=3;i<=x;i++){
      z=x+y;
      x=y;
      y=z;
}
cout<<z;
}

Последний метод работает, потому что вам нужны только предыдущие 2 числа Фибоначчи для создания текущего.

Answer 4

algorithm Fibonacci(x):
  stack = [1,1]
  while stack.length < x
    push to the stack the sum of two topmost stack elements
  return stack.last

Вы можете сохранить стек между вызовами как своего рода кеш.

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