ループ

Halflife2ばっかやってないで，id:yaneurao:20041128の問題を考えてみました．

つまるところ，ループというのは再帰関数に等しいわけです．例えば，

A a = A.begin;
do {
	do_something();
} while (a != A.end && ++a)

というプログラムは，

void hoge(A a)
  do_something();
  if (a==A.end) return;
  hoge(++a);
}

hoge(A.begin);

というプログラムをループに展開したものと考えられます．このプログラムは，先に示したプログラムと全く同じなので，後判定であると言えるでしょう．つまり，普通に定義した再帰的なアルゴリズムをループに展開すると，後判定になるということです．

ここで，Aの構造を考えてみると，これはA.endという空集合をベースケースとした再帰的な構造であると考えられます．*1

さらに，再帰的な構造に関しては，再帰的なアルゴリズムが簡単に定義できますし，わかりやすいです．つまり，再帰的なデータ構造を処理するプログラムは，アルゴリズム自体が本質的に再帰的に記述される，と言えるでしょう．

以上より，

1. 再帰的なアルゴリズムを普通に展開すると後判定のループになる
2. 良く使われるデータ構造は再帰的に定義できることが多い
3. 再帰的なデータ構造を処理するアルゴリズムは再帰的に定義される

と言えます．そして，上の1,2,3より直ちに「良く使われるデータ構造の上に定義された，再帰的なアルゴリズムは，後判定のループで記述される」と導くことができます．

これが後判定のループが頻繁に利用される理由です．

なんて，どうでしょうか．

*1:言うまでもなく，自然数やリストといった良く利用されるデータ構造は，再帰的に定義されます．配列は・・・リストでいいですよね？