再帰呼び出しをループに置き換える

半年に一度くらい、古いコードで使っている再帰呼び出しが原因でスタックオーバーフローになるという不具合が発見され、その都度ループで書き直す修正を入れている。再帰呼び出しをループに展開する方法は、「幅優先探索」や「深さ優先探索」というキーワードで探すと見つけることができる。そのエッセンスだけメモしておく。

再帰呼び出しのうち、トップダウンで処理していくものについては、キューを使うと比較的簡単に展開できる。たとえば

struct Node {
  Node* left;
  Node* right;
  :
};

という構造体があって、

void ProcessNode(Node* node)
{
  :
  : (do something)
  :

  if (node->left)
    ProcessNode(node->left);

  if (node->right)
    ProcessNode(node->right);
}

のような再帰呼び出しがあるとき、ProcessNode関数は以下のように展開できる。

void ProcessNode(Node* node)
{
  list<Node*> nodeList;
  nodeList.push_back(node);

  while (!nodeList.empty())
  {
    node = nodeList.front();
    nodeList.pop_front();

    :
    : (do something)
    :

    if (node->left)
      nodeList.push_back(node->left);

    if (node->right)
      nodeList.push_back(node->right);
  }
}

ボトムアップに処理していくものも基本的な考え方は一緒であるが、

1. キューの代わりにスタックを使う
2. スタックを積むときと実際に処理をするときの二度、ノードを訪れることになるので、今どっちのタイミングなのか、知るためのフラグが必要

になる点が少し面倒になる。模擬コードは以下のようになるはず（自分で試してね）。

namespace {
  struct Data {
    Data(Node* n) : node(n), isTraversed(false) {}
    Node* node;
    bool isTraversed;
  };
}

void ProcessNode(Node* node)
{
  vector<Data> nodeList;
  nodeList.push_back(node);

  while (!nodeList.empty())
  {
    auto& data = nodeList.back();
    node = data.node;

    if (!data.isTraversed)
    {
      data.isTraversed = true;

      if (node->left)
        nodeList.push_back(node->left);

      if (node->right)
        nodeList.push_back(node->right);
    }
    else
    {
      nodeList.pop_back();
      :
      : (do something)
      :
    }
  }
}

再帰呼び出しで書くと、単にコード中の "do something" の位置を if 文の前に持ってくるか後ろに置くかだけの差であり、記述としては簡便なうえに、マシンスタックを利用したほうがヒープよりも高速に動作する。つまりスタックオーバーフローを起こさない限りは再帰のほうが一概に優れているので、もろもろ考慮してどちらの実装方法を選ぶか決めましょう。