多重再帰構文!!
をテンプレートにして作成
[
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
メニュー
]
開始行:
これは,[[多重再帰構文!]]について,最近の知見を含めて解...
*多重再帰構文!! [#r1734d10]
多重再帰構文というのは,再帰関数の引数に再帰関数を含むよ...
この書き方には,''関数定義内の&color(red){ある変数より前}...
**迂遠なイントロダクション!! [#r0fff755]
[[Xを1つ含む関数]]に出てきた例を少し改変した,以下のコー...
x(X):rslXsX
a:x(x()x())x()rsslx()x()la
rsla
実行行の「rsl」,そしてaの定義内の「rssl」の部分を以下の...
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より前の部分を利...
同じような例をもう1つみてみましょう.今度はxが2変数です.
x(X,Y):ssXXslYlX
a(X):ssllslx(,)x(X,lX)ssa(--)
a(x(,))
「--」の部分は適当なコードだと思ってください.まず,先の...
a(X):ssllslx(,)x(X,lX)x(a(--),)
と短縮できますね.x(X,Y)のXに無限再帰a(-,-)を代入している...
さらに,前の「ssllsl」の部分が
a(X):x(l,x(,)x(X,lX)x(a(--),))
で書けてしまいます! x(X,Y)のYに無限再帰(を含むもの)を...
どちらの短縮も,''関数定義内の或る変数より前を即席の補助...
些細な補足ですが,今の例を少しだけ変えて,
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に...
さて,ここまでの例で(非再帰)関数xの変数に再帰関数aを代...
本記事で扱う多重再帰というのは,'''再帰関数'''の変数に再...
**実行行の多重再帰 [#lc3a49af]
イントロダクションの内容を念頭に,以下のコードを見てみま...
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より前の「s...
多変数の例もみてみましょう.
a(X,Y):slXXsXrYYsa(-,-)
slslsrslssssra(-,-)
関数定義のYの前の「slXXsXr」,そしてXの前の「sl」を利用し...
a(X,Y):slXXsXrYYsa(-,-)
a(a(,a(s,a(-,-))),)
と短縮できます.
これもやはりイントロダクションの例の延長上にある発想です...
実行行での多重再帰にはもう少し変態的な使い方もあるのです...
**関数定義内の多重再帰1 [#gfc66991]
***1変数 [#t9617944]
以下のコード:
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(--))))))
***2変数以上 [#pdd786b4]
多変数の場合も「基本的には」考え方は同じです.例えば:
a(X,Y):ssXssYsslssa(-,-)
Yの前の「ssXss」のXに「l」を代入した「sslss」という形が後...
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で初めて多変数多重再帰の...
**関数定義内の多重再帰2〜とあるテク [#k8957bb0]
実は,多変数の多重再帰ではもう少し変なこともできます.
先程の例をもう一度見てみましょう.
a(X,Y):XXXXYYYYYa(-,-)
「XXXX」に「Y」を代入した「YYYY」を「a(Y,」で置き換えて
a(X,Y):XXXXYa(Y,a(-,-))
と縮めたのでした.1つ目のYよりも後ろで多重再帰しているこ...
ところで,この例で「YYYY」という文字列はもう1通りあります...
a(X,Y):XXXX[YYYY]Ya(-,-)
では,この部分を同じように多重再帰で
a(X,Y):XXXXa(Y,Ya(-,-))
と書くこともできるのでしょうか?
結論から言うと,''できます''.~
つまり,Yの前を使って縮める部分が,1つ目のY以前から始まっ...
&size(5){展開してみると…(後で書く)};
そのような例をいくつかみてみましょう.
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縮みました.やべぇ
これまでの例に輪をかけて反直感的なコードですね.このよう...
見た目はやべぇですが,ここまでと同じように''ある変数の前...
''問題例'':[[Problem 2017]] タイトルが親切.
**応用 [#f6862c9f]
問題を解いたら自然に多重再帰が使える形になっている,とい...
***「変数の前の部分」をいじる [#pd5b0cce]
多重再帰は関数定義内のある変数より前を利用するテクニック...
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」に...
a(X,Y):lXXa(Y,sXa(sX,Ylsrs))
a(,l)
と書けて,差し引き1B縮みました.
***再帰関数の変数を増やす [#h8bd0d3d]
「利用したい部分」の後ろに変数を入れて多重再帰を使える形...
[[Problem 2021]]を例にみてみましょう.この問題は,素直に...
a(X):XXXlXXlXXla(sX)
a()
こんな感じの16Bコードになります.変数変換で14Bにすること...
a(X,Y):XXXYlXXYlXXYla(sX,)
a(,)
あえてYという変数を増やします.Yの前は「XXX」で,これに「...
a(X,Y):Xa(XXYl,a(sX,))
a(,)
と書くことができます!
''問題例'':[[Problem 0090]] 素直に書くと0変数再帰10Bに...
''問題例'':[[Problem 2030]] 素直に書くと1変数再帰14Bに...
**おまけ [#cd3a6ecb]
以下のmapを考えてみてください.Limitは12Bです.
#ref(MultiRecursion.png,nolink);
普通に再帰で大きい方から取ると13B,中心に戻ってから渦だと...
a(X):XXa(ssX)
llssa(l)
このコードをまず敢えて2変数にしてから,実行行で多重再帰を...
''問題例'':[[Problem 2019]]
展開してみるとわかりますが,関数定義の成長部分を使った,...
----
執筆:_misaki
終了行:
これは,[[多重再帰構文!]]について,最近の知見を含めて解...
*多重再帰構文!! [#r1734d10]
多重再帰構文というのは,再帰関数の引数に再帰関数を含むよ...
この書き方には,''関数定義内の&color(red){ある変数より前}...
**迂遠なイントロダクション!! [#r0fff755]
[[Xを1つ含む関数]]に出てきた例を少し改変した,以下のコー...
x(X):rslXsX
a:x(x()x())x()rsslx()x()la
rsla
実行行の「rsl」,そしてaの定義内の「rssl」の部分を以下の...
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より前の部分を利...
同じような例をもう1つみてみましょう.今度はxが2変数です.
x(X,Y):ssXXslYlX
a(X):ssllslx(,)x(X,lX)ssa(--)
a(x(,))
「--」の部分は適当なコードだと思ってください.まず,先の...
a(X):ssllslx(,)x(X,lX)x(a(--),)
と短縮できますね.x(X,Y)のXに無限再帰a(-,-)を代入している...
さらに,前の「ssllsl」の部分が
a(X):x(l,x(,)x(X,lX)x(a(--),))
で書けてしまいます! x(X,Y)のYに無限再帰(を含むもの)を...
どちらの短縮も,''関数定義内の或る変数より前を即席の補助...
些細な補足ですが,今の例を少しだけ変えて,
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に...
さて,ここまでの例で(非再帰)関数xの変数に再帰関数aを代...
本記事で扱う多重再帰というのは,'''再帰関数'''の変数に再...
**実行行の多重再帰 [#lc3a49af]
イントロダクションの内容を念頭に,以下のコードを見てみま...
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より前の「s...
多変数の例もみてみましょう.
a(X,Y):slXXsXrYYsa(-,-)
slslsrslssssra(-,-)
関数定義のYの前の「slXXsXr」,そしてXの前の「sl」を利用し...
a(X,Y):slXXsXrYYsa(-,-)
a(a(,a(s,a(-,-))),)
と短縮できます.
これもやはりイントロダクションの例の延長上にある発想です...
実行行での多重再帰にはもう少し変態的な使い方もあるのです...
**関数定義内の多重再帰1 [#gfc66991]
***1変数 [#t9617944]
以下のコード:
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(--))))))
***2変数以上 [#pdd786b4]
多変数の場合も「基本的には」考え方は同じです.例えば:
a(X,Y):ssXssYsslssa(-,-)
Yの前の「ssXss」のXに「l」を代入した「sslss」という形が後...
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で初めて多変数多重再帰の...
**関数定義内の多重再帰2〜とあるテク [#k8957bb0]
実は,多変数の多重再帰ではもう少し変なこともできます.
先程の例をもう一度見てみましょう.
a(X,Y):XXXXYYYYYa(-,-)
「XXXX」に「Y」を代入した「YYYY」を「a(Y,」で置き換えて
a(X,Y):XXXXYa(Y,a(-,-))
と縮めたのでした.1つ目のYよりも後ろで多重再帰しているこ...
ところで,この例で「YYYY」という文字列はもう1通りあります...
a(X,Y):XXXX[YYYY]Ya(-,-)
では,この部分を同じように多重再帰で
a(X,Y):XXXXa(Y,Ya(-,-))
と書くこともできるのでしょうか?
結論から言うと,''できます''.~
つまり,Yの前を使って縮める部分が,1つ目のY以前から始まっ...
&size(5){展開してみると…(後で書く)};
そのような例をいくつかみてみましょう.
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縮みました.やべぇ
これまでの例に輪をかけて反直感的なコードですね.このよう...
見た目はやべぇですが,ここまでと同じように''ある変数の前...
''問題例'':[[Problem 2017]] タイトルが親切.
**応用 [#f6862c9f]
問題を解いたら自然に多重再帰が使える形になっている,とい...
***「変数の前の部分」をいじる [#pd5b0cce]
多重再帰は関数定義内のある変数より前を利用するテクニック...
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」に...
a(X,Y):lXXa(Y,sXa(sX,Ylsrs))
a(,l)
と書けて,差し引き1B縮みました.
***再帰関数の変数を増やす [#h8bd0d3d]
「利用したい部分」の後ろに変数を入れて多重再帰を使える形...
[[Problem 2021]]を例にみてみましょう.この問題は,素直に...
a(X):XXXlXXlXXla(sX)
a()
こんな感じの16Bコードになります.変数変換で14Bにすること...
a(X,Y):XXXYlXXYlXXYla(sX,)
a(,)
あえてYという変数を増やします.Yの前は「XXX」で,これに「...
a(X,Y):Xa(XXYl,a(sX,))
a(,)
と書くことができます!
''問題例'':[[Problem 0090]] 素直に書くと0変数再帰10Bに...
''問題例'':[[Problem 2030]] 素直に書くと1変数再帰14Bに...
**おまけ [#cd3a6ecb]
以下のmapを考えてみてください.Limitは12Bです.
#ref(MultiRecursion.png,nolink);
普通に再帰で大きい方から取ると13B,中心に戻ってから渦だと...
a(X):XXa(ssX)
llssa(l)
このコードをまず敢えて2変数にしてから,実行行で多重再帰を...
''問題例'':[[Problem 2019]]
展開してみるとわかりますが,関数定義の成長部分を使った,...
----
執筆:_misaki
ページ名: