Techniques of Recursion のバックアップ(No.3)

Replace in a recursive function

a(X):XXXXrXXXXla(srslX)
a(r)
(20B)

The code above can be compressed by replacing XXXX by another variable.

a(X,Y):YrYla(srslX,XXXX)
a(r,)
(19B)

a(X,Y):YrYla(srslX,XXXX)
a(r,sss)

Even if you replace something by Y, the rule of Y isn't applied for "1st Y".
Thus, you can use "1st Y" freely.

a(X,Y):XYXa(XX,l)
a(srsl,r)

a(X,Y):XXXXYa(sX,YYl)
a(r,)

In this code, "1st Y" and "2nd Y" is special.

f(X):ssXlssf(sX)
f()
(12B)

This code can be compressed by recycling "ss"：

f(X):ssXlf(f(sX))
f()
(11B)

育たない再帰とかで