4

すべての再帰関数は反復に変換できますか? 反復を使用して再帰関数を実装するには、再帰関数にどのような特性が必要ですか?

反復を使用して次の関数を定義しようとしましたが、うまくいかないようです! 迷路内のすべてのパス (ノード) を探索することになっています。誰でも反復を使用してこれを書き直すことができますか? それが不可能な場合、それはなぜですか?

typedef int[0,99] id_t;
bool visited[id_t];
int path[id_t];
int pathCounter = 0;

struct { 
    id_t id;
    bool free;
    int neighborNode[4];
} nodeMap[id_t];

void findPath(int current){
    visited[current] = true;
    for (i : int[0, 3]){
        if(nodeMap[nodeMap[current].neighborNode[i]].free == true && visited[nodeMap[current].neighborNode[i]] == false && nodeMap[current].neighborNode[i] != -1){
        path[pathCounter] = nodeMap[nodeMap[current].neighborNode[i]].id;
        pathCounter++;
        findPath(nodeMap[current].neighborNode[i]);
        path[pathCounter] = nodeMap[current].id;
        pathCounter++;      
        }
    }
    path[0] = current;
}

拡張機能: 独自のスタックを実装せずに、前述の再帰関数を反復に変換することは可能ですか? 答えの 1 つは、スタック構造を使用せずにすべての末尾再帰関数を反復に変換できることを示唆していました...そうであれば、すべての再帰関数は末尾再帰に変換できますか? どのように？

4

5 に答える 5

7

はい、すべての再帰関数は、かなり機械的なプロセスに従うことで反復関数に変換できます。

コンパイラは、通常CPUのハードウェアに実装されているスタックを使用して再帰を実装することを思い出してください。独自のソフトウェアスタックを構築し、関数の状態（つまりローカル変数）を維持するのに適したものにし、初期状態をそのスタックにプッシュし、while新しい状態をスタックにプッシュするループを作成することができます。再帰呼び出し、戻る代わりにスタックをポップし、スタックが空でない間プロセスを続行します。

于 2012-07-29T11:48:37.943 に答える
5

通常、再帰的アルゴリズムをループに変換することは可能です。メソッドは単純です。コンパイラーが関数呼び出し用のコードを生成する方法を模倣できます。関数を入力し、関数から戻り、実行を続行します。

再帰関数を反復ループに変えるには、次のことができます。

  • 関数とローカル変数への引数を格納するレコードを定義します。これはスタックフレームに相当します。
  • プッシュを記録するスタックを定義します。これは、プログラムスタックに類似しています。
  • 関数が呼び出されたら、引数とローカル変数の現在の値のレコードを作成し、スタックにプッシュします。
  • 関数から戻るときは、スタックからポップアウトし、現在の値をレコードの値で上書きします。

上記のプロセス全体はwhileループで実行され、スタックが空になると終了します。

于 2012-07-29T11:50:37.100 に答える
3

すでに述べた他の回答と同様に、スタックをシミュレートすることでそれを行うことは技術的に可能です。しかし、あなたはそれをしたくないと思います。おそらく、スタックを使用せずに反復ソリューションが必要になるでしょう。その場合は、末尾再帰関数が必要です。AFAIR それが唯一の可能な方法です。スタックをシミュレートせずに、すべての末尾再帰関数を命令型関数に書き換えることができます。

于 2012-07-29T12:32:59.533 に答える
0

単純な「末尾」再帰がある場合は、代わりにループを使用できます（階乗関数など）。より複雑な関数では、stack構造体とwhile (!stack.empty())ループを使用する必要があります。ただし、、、、などの非常に複雑な再帰がある場合はTowers of Hanoi、前と同じようにwithループを使用する必要がありますがMerge Sort、ステートメントを使用して現在の呼び出しステータスを判別します。printing truth tablestackwhileswitch

再帰的：

void mergeSort(int start, int end)
{
    if (start < end)
    {
         mergeSort(start, (start + end) / 2);
         mergeSort((start + end) / 2 + 1, end);
         Merge(start, end);
    }

}

反復：

void mergeSort()
{
  stack<int> st;
  st.push(1);
  int status;

  while (!st.empty())
  {
      status = st.pop();
      switch (status)
      {
        case 1:
             ....
            break;
        case 2:
             break;
      }
  }
}

プロセスを詳細に説明しているこの優れたPDFを強くお勧めします。

于 2012-07-29T12:39:52.853 に答える
-3

http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Recursion_versus_iterationによると、再帰的に定義されたすべての関数は反復関数に変換できます。

于 2012-07-29T11:37:12.953 に答える