IT戦記

「再帰→ループ」の変換が大変だった件

JavaScript

まず、ループは再帰で表現できる

ループというのはすべて再帰呼び出しで表現できる。

たとえば、コレは

var array = [1, 2, 3];
for (var i = 0; i < array.length; i ++) alert(array[i]);

こんな感じになる

(function f(array, i) {
  if (i < array.length) {
    alert(array[i]);
    return f(array, i+1);
  }
})([1, 2, 3], 0);

もし、 array がこの目的以外に使われないならコッチのがキレイかも

(function f(array) {
  alert(array.shift());
  if (array.length) return f(array);
})([1, 2, 3]);

ということは、再帰はループで表現できるはず

ということで、 document ノードから全部の DOM を再帰的に辿っていく例をループで表現してみようと思った

まずは、元のコード

(function f(node) {
  console.log(node);
  for (node = node.firstChild; node; node = node.nextSibling) f(node);
})(document);

これをループで表現してみる。

まず、 for 文を while 文に分解。

(function f(node) {
  console.log(node);
  node = node.firstChild;
  while (node) {
    f(node);
    node = node.nextSibling;
  }
})(document);

次に、 function を goto 文とスタックに分解。

var stack = [];
var node = document;

f:
console.log(node);
node = node.firstChild;
while (node) {
  stack.push(node);
  goto f;
ret:  
  node = node.nextSibling;
}
node = stack.pop();
if (stack.length) goto ret;

次に、 f から goto f をループで表現します。 ret: 以下の部分は外に出します。

var stack = [];
var node = document;

while (true);
  console.log(node);
  node = node.firstChild;
label0:
  if (!node) goto label1;
  stack.push(node);
}

ret:
node = node.nextSibling;
goto label0;

label1:
node = stack.pop();
if (stack.length) goto ret;

だんだんコードがスパゲッティになってきました。。

次に、 ret には goto 文以外で到達するケースがないため、自由に移動できます。

var stack = [];
var node = document;

while (true) {
  console.log(node);
  node = node.firstChild;
label0:
  if (!node) goto label1;
  stack.push(node);
}

label1:
node = stack.pop();
if (stack.length) goto ret;
else goto end;

ret:
node = node.nextSibling;
goto label0;

end:

次に goto label1 を break にして、 goto ret を削除します。

var stack = [];
var node = document;

while (true) {
  console.log(node);
  node = node.firstChild;
label0:
  if (!node) break;
  stack.push(node);
}

node = stack.pop();

if (stack.length) {
  node = node.nextSibling;
  goto label0;
}

次に、 label0 を while ループの外に出します。無限ループは巻き紙のようなものなので、一行ずつ上にずらして一番上の行を外に出していけば OK です。

var stack = [];
var node = document;

console.log(node);
node = node.firstChild;
label0:
while (true) {
  if (!node) break;
  stack.push(node);
  console.log(node);
  node = node.firstChild;
}

node = stack.pop();

if (stack.length) {
  node = node.nextSibling;
  goto label0;
}

次に、 goto label0 をループで表現します。

var stack = [];
var node = document;

console.log(node);
node = node.firstChild;

while (true) {

  while (true) {
    if (!node) break;
    stack.push(node);
    console.log(node);
    node = node.firstChild;
  }

  node = stack.pop();

  if (stack.length) {
    node = node.nextSibling;
  }
  else break;
}

あとは、少しコードをキレイにして

var stack = [];
var node = document;

console.log(node);
node = node.firstChild;

while (true) {

  while (node) {
    stack.push(node);
    console.log(node);
    node = node.firstChild
  }

  node = stack.pop();
  if (!stack.length) break;
  node = node.nextSibling;
}

はい！完成！わーわーぱちぱちぱち。

まとめ

関数呼び出しをやめてみて、関数呼び出しやスタックフレームの理解がほんの少しだけ深まったような気がします。

ツイートする

Permalink | コメント(4) | トラックバック(1) | 17:11