c - 如何正确使用循环和堆栈来模拟递归？

Question

(我的英语不好，所以我的表达可能不太清楚和正确。)

我想通过使用循环和堆栈来模拟递归。

我的目标不是如何提高性能，因为解决斐波那契的原始递归方法也非常无效。而且模拟很难有更好的性能。我想知道如何将递归更改为循环和堆栈。

求解斐波那契数列的递归版本(只是递归的一个例子)。很简单

int fib(int i)
{
    if (i == 0)
        return 0;
    if (i == 1)
        return 1;
    return fib(i - 1) + fib(i - 2);
}

这是我对递归的模拟

int fib2(int a)
{
    Stack *stack = NULL;
    int temp = -1;
    int i[3] = {a, -1, -1};
    stack = stack_push(stack, i);
    while(!stack_empty(stack))
    {
        int *top = stack_top(stack);
        if (temp != -1 && top[1] == -1)
        {
            top[1] = temp;
            temp = -1;
        }
        else if(temp != -1 && top[2] == -1)
        {
            top[2] = temp;
            temp = -1;
        }
        if (top[0] == 0)
        {
            stack = stack_pop(stack);
            temp = 0;
            continue;
        }
        else if(top[0] == 1)
        {
            stack = stack_pop(stack);
            temp = 1;
            continue;
        }
        else
        {
            int j[3] = {top[0], -1, -1};
            if (top[1] == -1)
            {
                j[0] = top[0] - 1;
                stack = stack_push(stack, j);
            }
            else if (top[2] == -1)
            {
                j[0] = top[0] - 2;                
                stack = stack_push(stack, j);
            }
            else
            {
                temp = top[1] + top[2];
                stack = stack_pop(stack);
            }
            continue;
        }
    }
    return temp;
}

栈是通过链表实现的，相关功能非常简单。它工作得很好，但我认为我这样做的方式太迟缓和困难。

我只是想知道怎样才能做得更容易？ (不是用循环来求解斐波那契，而是模拟递归)

我真正关心的是如何处理超过1个递归函数调用。

对于 1 个这样的函数调用。

int sum(int i)
{
    if (i == 0)
        return 0;
    return i + sum(i - 1);
}

使用循环和堆栈来模拟非常容易。而且也有效。

int sum2(int a)
{
    Stack *stack = NULL;
    while (a > 0)
    {
        stack = stack_push(stack, a);
        a--;
    }
    int i = 0;
    while (!stack_empty(stack))
    {
        i += stack_top(stack);
        stack = stack_pop(stack);
    }
    return i;
}

但是对于超过1次的调用，我所知道的只是使用这样一个愚蠢的方式来做(用-1作为标志)。

Answer 1

我不明白为什么递归方法不好，但如果你想用循环来做到这一点，那应该不会太难，我为你准备了一些“某种”伪代码，你不需要甚至需要一个链表，这应该会大大降低程序的计算复杂性。

int main() {
  int fib_max = 10;

  int node_1 = 0;
  int node_2 = 0;
  int node_s = 0;

  for ( int n = 0; n < fib_max; n ++)
    {
      if (node_2 == 0)
    node_2 = 1;

      node_s = node_2 + node_1;
      node_1 = node_2;
      node_2 = node_s;
    }
}

这只是我自己编的，希望对你有帮助。