ループとスタックを使って再帰を正確にシミュレートするにはどうすればいいですか？

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をつける）だけです。

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; 
    } 
} 

これは私が料理したものです。うまくいけば、それはあなたを助けます。