![[PukiWiki]](image/hojwiki.png "[PukiWiki]")
これは，多重再帰構文！について，最近の知見を含めて解説してみようという記事です．
多重再帰構文というのは，再帰関数の引数に再帰関数を含むようなコードを指します．
この書き方には，関数定義内のある変数より前を利用できるという効果があります．これを説明するために，まずはあえて再帰しない関数の例からみてみましょう．
Xを1つ含む関数に出てきた例を少し改変した，以下のコードを見てみましょう．
x(X):rslXsX a:x(x()x())x()rsslx()x()la rsla
実行行の「rsl」，そしてaの定義内の「rssl」の部分を以下のようにxで書いて短縮できますね．
x(X):rslXsX a:x(x()x())x()x(x(x()x()la)) x(a)
4B縮みました．関数xの引数に再帰関数aを代入しているので，慣れていない人には盲点に入りやすい短縮かもしれません． 今短縮したところを展開してみると，
x(X):rslXsX a:x(x()x())x()rslrslx()x()lasx()x()lasrslx()x()lasx()x()la rslasa
となりますが，無限再帰aより右は実行されることはないので，そこを削れば
x(X):rslXsX a:x(x()x())x()rslrslx()x()la rsla
と，元のコードに一致しますね．
これを掘り下げて考えてみましょう．x(X)のXに無限再帰を含むものを代入すると，x(X):rslXsXの1つ目のXより後ろは実行されず，結果的にはまずXより前の「rsl」が実行されて，それから代入したものが実行されます．実質的には代入したものの前に「rsl」をつけただけとなっていますね．
つまり，この短縮はxの関数定義内の変数Xより前の部分を利用したと見做せるわけです．
同じような例をもう1つみてみましょう．今度はxが2変数です．
x(X,Y):ssXXslYlX a(X):ssllslx(,)x(X,lX)ssa(--) a(x(,))
「--」の部分は適当なコードだと思ってください．まず，先の例と同じ考え方で，「ssa(--)」の部分が
a(X):ssllslx(,)x(X,lX)x(a(--),)
と短縮できますね．x(X,Y)のXに無限再帰a(-,-)を代入しているので，関数定義「x(X,Y):ssXXslYlX」のXより前の「ss」をつけたのと同じことになっています．
さらに，前の「ssllsl」の部分が
a(X):x(l,x(,)x(X,lX)x(a(--),))
で書けてしまいます！ x(X,Y)のYに無限再帰（を含むもの）を代入していて，「ssXXslYlX」のYより前の部分「ssXXsl」のXにlを入れて「ssllsl」として利用しています．
どちらの短縮も，関数定義内の或る変数より前を即席の補助関数として利用している*1のがわかると思います．
些細な補足ですが，今の例を少しだけ変えて，
x(X,Y):ssXXslYlX a(X):ssXrXrslx(,)x(X,lX)ssa(--) a(x(,))
としてみましょう．aの定義内のllをXrXrに変えただけです．
x(X,Y):ssXXslYlX a(X):x(Xr,x(,)x(X,lX)x(a(--),)) a(x(,))
と短縮できますね．先程と全く同様の短縮ですが，x(X,Y)のXにaの変数を入れてもOK，というのは少し見落としがちかもしれません．
さて，ここまでの例で（非再帰）関数xの変数に再帰関数aを代入したときの効果を見てきました． 本記事で扱う多重再帰というのは，再帰関数の変数に再帰関数を代入しても同じようなことができるよね！というテクニックです．
イントロダクションの内容を念頭に，以下のコードを見てみましょう．
a(X):ssXlXa(--) ssssla(r)
実行行の「ssss」を
a(X):ssXlXa(--) a(a(la(r)))
と，aを再利用して書いてしまうことができます！ 実行行を展開してみると
ssssla(r)lla(r)a(--)la(r)lla(r)a(--)
となっていて，無限再帰「a(r)」以降を削ると元の実行行に一致することが確かめられます．
a(X)のXに無限再帰を代入したので，関数定義内のXより前の「ss」だけが実行されているわけです．イントロダクションの例と同じ考え方ですね．
多変数の例もみてみましょう．
a(X,Y):slXXsXrYYsa(-,-) slslsrslssssra(-,-)
関数定義のYの前の「slXXsXr」，そしてXの前の「sl」を利用して，
a(X,Y):slXXsXrYYsa(-,-) a(a(,a(s,a(-,-))),)
と短縮できます． これもやはりイントロダクションの例の延長上にある発想ですね．
実行行での多重再帰にはもう少し変態的な使い方もあるのですが，これについては最後の「おまけ」の節で触れることにします．
以下のコード：
a(X):ssXlssa(sXs) a(r)
関数定義内で多重再帰することで，
a(X):ssXla(a(sXs)) a(r)
と短縮できます．展開してみると，
a(X):ssXlssa(sXs)la(sa(sXs)s)
となっていて，無限再帰「a(sXs)」以降を削ると元のコードと一致します．今まさに定義している最中の関数を利用しているので，かなり意外な短縮ですね．
発想としては前の例と全く同様で，無限再帰を代入すると，定義内の変数の前の部分をつけるのと同じ効果が得られます．
問題例：Problem 1687 HOJで初めて多重再帰が想定解として出題された問題．
もちろんここまでの例と同様，3重以上にもできます．
a(X):ssXssssXssssssa(--) → a(X):ssXa(a(Xa(a(a(a(--))))))
多変数の場合も「基本的には」考え方は同じです．例えば：
a(X,Y):ssXssYsslssa(-,-)
Yの前の「ssXss」のXに「l」を代入した「sslss」という形が後ろにあるので，そこを「a(l,〜」で置き換えて
a(X,Y):ssXssYa(l,a(-,-))
と書けます．さらに，Xの前の「ss」も使って，
a(X,Y):ssXa(Ya(l,a(-,-),)
元のコードからかなり縮みましたね．
問題例：Problem 1902 HOJで初めて多変数多重再帰が想定解として出題された問題（たぶん）．
似たコードをみてみましょう．
a(X,Y):ssXrXssYsslYXYXssa(-,-)
Yの前の「ssXrXss」のXに「lYX」を入れた「sslYXYXss」という形が後ろにあるので，
a(X,Y):ssXrXa(Ya(lYX,a(-,-)),)
と書けますね．変数を入れてもいい，というのはやや見落としやすいポイントかもしれません．
では，この関数↓はどう縮められるでしょう？
a(X,Y):XXXXYYYYYa(-,-)
Yの前が「XXXX」，このXに「Y」を代入した形があるので
a(X,Y):XXXXYa(Y,a(-,-))
と2B縮みますね．
問題例：Problem 1975 HOJで初めて多変数多重再帰の1つ目の引数に変数を代入するのが想定解として出題された問題（たぶん）．
実は，多変数の多重再帰ではもう少し変なこともできます． 先程の例をもう一度見てみましょう．
a(X,Y):XXXXYYYYYa(-,-)
「XXXX」に「Y」を代入した「YYYY」を「a(Y,」で置き換えて
a(X,Y):XXXXYa(Y,a(-,-))
と縮めたのでした．1つ目のYよりも後ろで多重再帰していることに注目してください．ここまでのコード例でも，Yに無限再帰を代入するときは，どれも関数定義のYよりも後ろで多重再帰していました．
ところで，この例で「YYYY」という文字列はもう1通りありますね↓（[]で囲った部分）
a(X,Y):XXXX[YYYY]Ya(-,-)
では，この部分を同じように多重再帰で
a(X,Y):XXXXa(Y,Ya(-,-))
と書くこともできるのでしょうか？
結論から言うと，できます．
つまり，Yの前を使って縮める部分が，1つ目のY以前から始まっていても良いのです．
展開してみると…（後で書く）
そのような例をいくつかみてみましょう．
a(X,Y):XlXYllXYa(-,-)
Yの前が「XlX」で，それに「lXY」を代入した「lXYllXY」があるので，
a(X,Y):Xa(lXY,a(-,-))
と短縮できます．やべぇ
また，こんなコード：
a(X,Y):ssXssXYssXYa(Y,sX) a(r,)
「ssXssX」に「XY」を代入した形の「ssXYssXY」を「a(XY,」で置き換えて，
a(X,Y):ssXa(XY,a(Y,sX)) a(r,)
5B縮みました．やべぇ
これまでの例に輪をかけて反直感的なコードですね．このようなコードは，KtyaさんがProblem 1975の別解として発見したもので，「とあるテク」などと呼ばれています．
見た目はやべぇですが，ここまでと同じようにある変数の前を即席の補助関数として利用するだけなので，短縮自体は難しくないと思います．
問題例：Problem 2017 タイトルが親切．
問題を解いたら自然に多重再帰が使える形になっている，ということも勿論ありますが，多くの場合は「あえて多重再帰が使える形に変形する」→「多重再帰を使って短縮」というステップが必要になります．具体的な例をいくつか挙げてみます．
多重再帰は関数定義内のある変数より前を利用するテクニックなので，その部分をうまいこといじるのは自然な発想でしょう．例えばこんなコード．
a(X):ssssssXla(XsXl) a()
Xの前は「ssssss」で，このままで特に縮みません．しかし，
a(X):sssXlsssa(XsXl) sssa()
とsssをずらすことで，実行行と関数定義で多重再帰が使えて
a(X):sssXla(a(XsXl)) a(a())
元のコードから1B縮みました．
お次はこんなコード．
a(X,Y):XlXXlYYla(sX,Ylsrs) a(,l)
Yの前は「XlXXl」で，この形では多重再帰は使えませんが，
a(X,Y):lXXlYYlsXa(sX,Ylsrs) a(,l)
このようにXを一つ後ろにずらすと，Yの前が「lXXl」になったので，「lYYl」の部分が
a(X,Y):lXXa(Y,sXa(sX,Ylsrs)) a(,l)
と書けて，差し引き1B縮みました．
「利用したい部分」の後ろに変数を入れて多重再帰を使える形にする，というのも有力な発想です．
Problem 2021を例にみてみましょう．この問題は，素直に解くと
a(X):XXXlXXlXXla(sX) a()
こんな感じの16Bコードになります．変数変換で14Bにすることもできますが，多重再帰を使うと13Bになります．このように↓
a(X,Y):XXXYlXXYlXXYla(sX,) a(,)
あえてYという変数を増やします．Yの前は「XXX」で，これに「XXYl」を入れた「XXYlXXYlXXYl」という箇所があるので，
a(X,Y):Xa(XXYl,a(sX,)) a(,)
と書くことができます！
問題例：Problem 0090 素直に書くと0変数再帰10Bになりますが…
問題例：Problem 2030 素直に書くと1変数再帰14Bになりますが…
以下のmapを考えてみてください．Limitは12Bです．
普通に再帰で大きい方から取ると13B，中心に戻ってから渦だと14Bかかってしまい，一見12B以下にはできなさそうに見えます．ところが，後者の方針で多重再帰を使うことで解けます．
a(X):XXa(ssX) llssa(l)
このコードをまず敢えて2変数にしてから，実行行で多重再帰を使うことで12Bにすることができます．答えは載せないので，是非考えてみてください．
問題例：Problem 2019
展開してみるとわかりますが，関数定義の成長部分を使った，段階を踏んだ多重再帰といった感じでしょうか．あまり汎用性があるテクではなさそう？
執筆：_misaki
MultiRecursion.png