0

自分自身を呼び出す別の関数なしで再帰を実装する方法（または可能であれば）を考えていました。これまでのところ、私が見た再帰を実装するすべてのアルゴリズムは、別の関数を使用しています。私はよく考えて、いくつかの変数の突然変異を伴うgotoステートメントが仕事をすることができるという考えを思いつきましたが、私はそれについて本当に確信が持てません. 私は簡単な調査を行い、この構造化プログラミング定理に関する情報を見つけました。これ は、すべてのアルゴリズムが 3 つのデータ構造のみで実装できることを証明しているため、そのような再帰実装は可能でなければなりませんが、すべてを一貫した知識にまとめて全体を理解することはまだできません。 -アプローチする。

4

3 に答える 3

2

あなたが探しているのは、基本的に再帰関数を反復形式に表現することです。これは、スタックを使用して簡単に実行できます。C# での非常に単純な例を次に示します。

int NodeCount(Node n)
{
      if (n.Visited) return 0; // This node was visited through another node, discard
      n.Visited = true;
      int res = 1;
      foreach (Node ni in n.Children) // Recurse on each node
      {
            res += NodeCount(ni); // Add the number of sub node for each node
      }
      return res;           
}

反復形式のまったく同じ関数を次に示します。

int NodeCount(Node root)
{
    int res = 0;
    Stack<int> stk = new Stack<int>();
    stk.Push(root) // We start with the root node
    while( stk.Count > 0) // While we still have nodes to visit
    {
          Node current = stk.Pop(); // Get the node on top of the stack
          current.Visited = true;  // Mark it as visited
          res ++; // Add one to the count
          foreach (Node ni in n.Children) // Push all non visited children to the stack
          {     
                if (ni.Visited == false) 
                        stk.Push(ni);
          }

    }
    return res;
}
于 2012-09-21T20:24:41.673 に答える
1

スタックベースの言語を使用して、関数なしで一種の再帰を実行できます。たとえば、Forth では、次のようにフィボナッチ関数を記述できます。

: fibonacci 0 1 10 0 do 2dup + rot . ループスワップ。. ;

このプログラムは、フィボナッチ数列の 10 回の反復を再帰的に生成します。各反復は、前の反復からの入力を使用します。関数は呼び出されません。

于 2012-09-21T21:21:09.110 に答える
1

自分自身を呼び出す別の関数なしで再帰を実装します。

はい、再帰アルゴリズムを反復アルゴリズムに変換することは可能です。gotoしかし、なぜステートメントを使用したいのでしょうか? 関数呼び出しを行うと、生成されたアセンブリには、goto.
したがって、あなたが達成することは、機械語コードが最終的に行うことと多少似ていますが、スタック フレーム呼び出しを回避できるという利点と、goto.
再帰を避けたい場合は、繰り返しを使用してください。どうやってこの質問を思いついたのですか？

于 2012-09-21T20:24:20.283 に答える