繰り返しの回数が有限のときに、(有限個の)変更しない変数で書けることや関数の再帰的定義を取り除くことができること(また変数や関数定義を取り除くことができること)を示すための例を考えます。
平方根の例は長いので、ここではフィボナッチ数列の例を考えます。フィボナッチ数列は以下のように定義されます(wikipedia:フィボナッチ数を参照)。
C# のイテレーターを使って擬似的な無限の列を考えます。
IEnumerable<int> fib()
{
int x = 0;
int y = 1;
yield return x;
yield return y;
for (; ; )
{
int z = x + y;
yield return z;
x = y;
y = z;
}
}
最初の30項は以下のようになります。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229
繰り返しの回数が8回以内として「for」を「展開」して取り除き、変数を変更しないようにすると以下のようになります。
IEnumerable<int> fib()
{
int x_0 = 0;
int y_0 = 1;
yield return x_0;
yield return y_0;
int z_0 = x_0 + y_0;
yield return z_0;
int x_1 = y_0;
int y_1 = z_0;
int z_1 = x_1 + y_1;
yield return z_1;
int x_2 = y_1;
int y_2 = z_1;
int z_2 = x_2 + y_2;
yield return z_2;
int x_3 = y_2;
int y_3 = z_2;
int z_3 = x_3 + y_3;
yield return z_3;
int x_4 = y_3;
int y_4 = z_3;
int z_4 = x_4 + y_4;
yield return z_4;
int x_5 = y_4;
int y_5 = z_4;
int z_5 = x_5 + y_5;
yield return z_5;
int x_6 = y_5;
int y_6 = z_5;
int z_6 = x_6 + y_6;
yield return z_6;
int x_7 = y_6;
int y_7 = z_6;
int z_7 = x_7 + y_7;
yield return z_7;
}
結果は以下のようになります。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
fib() の中で fib() を参照するようにします。2つの数の和を取らなければいけないのですが、「foreach (…)」 の中では1つしか書くことができないので以下のようになります。
IEnumerable<int> fib()
{
yield return 0;
yield return 1;
IEnumerator<int> fib_itr = fib().GetEnumerator();
fib_itr.MoveNext();
foreach (int n in fib())
{
fib_itr.MoveNext();
yield return n + fib_itr.Current;
}
}
foreach をやめて for で書き直すと以下のようになります。
IEnumerable<int> fib()
{
yield return 0;
yield return 1;
IEnumerator<int> fib_itr1 = fib().GetEnumerator();
IEnumerator<int> fib_itr2 = fib().GetEnumerator();
fib_itr2.MoveNext();
for (; ; )
{
fib_itr1.MoveNext();
fib_itr2.MoveNext();
yield return fib_itr1.Current + fib_itr2.Current;
}
}
for を展開することはできるのですが、fib_itr1.MoveNext()、fib_itr2.MoveNext() で fib_itr1、fib_itr2 が更新されるので、C# のイテレーターを直接使うと変数が変更されないようにはできません。
IEnumerable<int> fib()
{
yield return 0;
yield return 1;
IEnumerator<int> fib_itr1 = fib().GetEnumerator();
IEnumerator<int> fib_itr2 = fib().GetEnumerator();
fib_itr2.MoveNext();
fib_itr1.MoveNext();
fib_itr2.MoveNext();
yield return fib_itr1.Current + fib_itr2.Current;
fib_itr1.MoveNext();
fib_itr2.MoveNext();
yield return fib_itr1.Current + fib_itr2.Current;
fib_itr1.MoveNext();
fib_itr2.MoveNext();
yield return fib_itr1.Current + fib_itr2.Current;
fib_itr1.MoveNext();
fib_itr2.MoveNext();
yield return fib_itr1.Current + fib_itr2.Current;
fib_itr1.MoveNext();
fib_itr2.MoveNext();
yield return fib_itr1.Current + fib_itr2.Current;
fib_itr1.MoveNext();
fib_itr2.MoveNext();
yield return fib_itr1.Current + fib_itr2.Current;
fib_itr1.MoveNext();
fib_itr2.MoveNext();
yield return fib_itr1.Current + fib_itr2.Current;
fib_itr1.MoveNext();
fib_itr2.MoveNext();
yield return fib_itr1.Current + fib_itr2.Current;
}
C# のイテレーターでは変数を変更しないようにはできなかったので、自作のイテレーターを作ります。
IEnumerable<int> fib()
{
int x = 0;
int y = 1;
int next()
{
int z = x + y;
x = y;
y = z;
return z;
}
yield return 0;
yield return 1;
for (; ; )
{
yield return next();
}
}
この next を変数を変更しないように書き直します。
IEnumerable<int> fib()
{
(int,int) next(int x, int y)
{
int z = x + y;
return (y, z);
}
int x = 0;
int y = 1;
yield return 0;
yield return 1;
for (; ; )
{
(x, y) = next(x, y);
yield return y;
}
}
そして for を展開すると変数を変更しないようにすることができます。
IEnumerable<int> fib()
{
(int, int) next(int x, int y)
{
int z = x + y;
return (y, z);
}
int x_0 = 0;
int y_0 = 1;
yield return 0;
yield return 1;
(int x_1, int y_1) = next(x_0, y_0);
yield return y_1;
(int x_2, int y_2) = next(x_1, y_1);
yield return y_2;
(int x_3, int y_3) = next(x_2, y_2);
yield return y_3;
(int x_4, int y_4) = next(x_3, y_3);
yield return y_4;
(int x_5, int y_5) = next(x_4, y_4);
yield return y_5;
(int x_6, int y_6) = next(x_5, y_5);
yield return y_6;
(int x_7, int y_7) = next(x_6, y_6);
yield return y_7;
(int x_8, int y_8) = next(x_7, y_7);
yield return y_8;
}
のとき
かつ 
のとき
のとき
