再帰関数の奏でる音楽

みなさん、「再帰関数」を "聴いた" ことありますか？

聴いたことがあるほうが珍しいと思うので、少し音楽を楽しんでいってください。

できた音楽たち

以下の画像をクリックするとyoutubeがひらきます。サムネイルが同じですが、ちゃんと別のリンクが拓きます。

たらいまわし関数

Tak関数

3変数アッカーマン関数

物語のはじまり

2011年、竹内関数（たらいまわし関数）で音楽を作る記事「竹内関数で音楽生成 」がでた。以下はその動画で、再帰関数から良い感じの音楽がつくられているのがわかる。

↑もとの動画

竹内関数（たらいまわし関数）

以下のような再帰関数だ。

\begin{eqnarray}
\text{Tarai}(x,y,z)=\left\{ \begin{array}{ll}
y & (x \leq y) \\
\text{Tarai}(\text{Tarai}(x-1,y,z),\text{Tarai}(y-1,z,x),\text{Tarai}(z-1,x,y)) & (otherwise) \\
\end{array} \right.
\end{eqnarray}

そもそも「再帰関数って何？」って方はけんちょんさんの記事「再帰関数を学ぶと、どんな世界が広がるか」に目を通すと完璧だと思う。

定義からもわかるように竹内関数では処理を再帰的に呼び出しておきながらも、引数 $z$ はif文に使わないのでとても無駄が多い。例えば$Tarai(10, 5, 0)$を呼び出すと、再帰呼び出しは343,073回となる。これがなぜ音楽と結びつくかについては以下に引用する。

この関数呼び出しの引数がどのように変化するか知りたくてプログラムを書いて調べてみたところ、Tarai(10,5,0)の場合は3つの引数がそれぞれ0〜10（xは-1〜10）の間で少しずつ変化するなかで、2つの値を固定してひとつの値が下降していくような挙動があったりして、なんだか音楽の3和音のコード進行を思わせるような動き方です。
　
そういうことなら、ということで実際に音にして聴いてみました。Tarai関数が呼ばれるたびに引数のx、y、zを、0=ミ、1=ファ、2=ソ、……、のように音に割りあて3和音にして鳴らしています。せっかくなので音源の自動アルペジオ機能でミニマルっぽくしています。この手の自動生成音楽にしては緊張感の変化があってちょっと面白いんじゃないかと思います。

音楽にする工夫

再帰関数の引数の数字をドレミに対応させて音楽をつくったようだ。下の表を見てほしい。

数字	-1	0	1	2	3	4	5	6	7	8	9	10
音	レ	ミ	ファ	ソ	ラ	シ	ド	レ	ミ	ファ	ソ	ラ

提案者によると

• 白鍵だけ使用する（#とか使わない）
• 最小値(-1)をレにしてドリアンスケールにした
• テンポや音色は工夫した

とのことで、私はこれを真似することにした。ここまでは既存の内容。

実装してみる

というわけで実際にやってみた。

MIDIとかわからないので、PythonレトロゲームエンジンPyxelを使用した。以下コード（やや長いです）。あとこの実装は †邪悪なGlobal変数† を使用しているので、ましな実装例は参考：クロージャを用いた実装を確認ください。

import pyxel
import sys
sys.setrecursionlimit(10_000_000) # 再帰上限の引き上げ

# †邪悪なグローバル変数†
cnt = 0  # 再帰呼び出し回数

# -1:レ, 0:ミ, ....に対応付ける
note = ["C3", "D3", "E3", "F3", "G3",
        "A4", "B4", "C4", "D4", "E4", "F4", "G4",
        "B3"]  # -1に対応する音

# 竹内関数の引数を音符にしたもの
melody_x = ""
melody_y = ""
melody_z = ""

# 描画用に引き数も保持しておく
xs = []
ys = []
zs = []


def tarai(x, y, z):
    """tarai(10, 5, 0) は-1～10で変化
    """
    global cnt
    global melody_x, melody_y, melody_z
    global xs, ys, zs
    
    cnt += 1
    if cnt >= 500:
        raise StopIteration("再帰呼び出し終わり―")

    # 引数を保持しておく
    melody_x += note[x]
    melody_y += note[y]
    melody_z += note[z]
    xs.append(x)
    ys.append(y)
    zs.append(z)

    # 再帰処理
    if x <= y:
        return y
    else:
        return tarai(tarai(x - 1, y, z),
                     tarai(y - 1, z, x),
                     tarai(z - 1, x, y))


def define_music(func_name: str):
    """関数にそって音楽を定義する
    """
    global melody_x, melody_y, melody_z
    SPEED = 20  # 120で1秒に一音, 一秒に120/SPEED回

    # 再帰回数500回まで記録
    try:
        if func_name == "tarai":
            tarai(10, 5, 0)
        elif func_name == "tak":
            tak(10, 5, 0)
        elif func_name == "ack":
            ack(1, 1, 1)
        else:
            raise ValueError("func_nameが不正：tarai, tak, ackのいずれかを指定してください")
    except ValueError as e:
        print(e)
    except StopIteration as e:
        print(e)

    # 各引数にそって音楽を定義
    pyxel.sound(2).set(
        note=melody_x,
        tone="s",
        volume="5",
        effect="n",
        speed=SPEED,
    )
    pyxel.sound(3).set(
        note=melody_y,
        tone="t",
        volume="5",
        effect="f",
        speed=SPEED,
    )
    pyxel.sound(4).set(
        note=melody_z,
        tone="n",
        volume="5",
        effect="f",
        speed=SPEED,
    )
    pyxel.music(0).set([], [2], [3], [4])


def update():
    pass


def draw():
    """鍵盤を描画する
    """
    _width = pyxel.width//14  # 鍵盤が14個あるので
    pyxel.cls(pyxel.COLOR_LIGHTGRAY)

    pyxel.rect(x=2, y=20, w=_width*14, h=60, col=pyxel.COLOR_WHITE)

    f = (pyxel.frame_count//5) % len(xs)
    
    # (竹内関数の引数+2)が鍵盤の場所に対応
    # ひく鍵盤に色を付ける
    pyxel.rect(x=2+_width*(xs[f]+2), y=20, w=_width,
               h=60, col=pyxel.COLOR_CYAN)
    pyxel.rect(x=2+_width*(ys[f]+2), y=20, w=_width,
               h=60, col=pyxel.COLOR_LIME)
    pyxel.rect(x=2+_width*(zs[f]+2), y=20, w=_width,
               h=60, col=pyxel.COLOR_YELLOW)

    # 鍵盤を描画
    for i in range(14):
        # 白鍵
        pyxel.rectb(x=2+_width*i, y=20, w=_width,
                    h=60, col=pyxel.COLOR_BLACK)
        # 黒鍵
        if i % 7 in [0, 1, 3, 4, 5]:
            pyxel.rect(x=2+_width*(i+2/3), y=20, w=(_width*2/3),
                       h=30, col=pyxel.COLOR_BLACK)


if __name__ == "__main__":
    pyxel.init(width=200, height=100, fps=30)

    define_music(func_name="tarai")
    pyxel.playm(0, loop=True) # 音楽を再生
    pyxel.run(update, draw)

こんな音が鳴った。（記事の最初のリンクを再掲。クリックで再生できる）。

提案者の音楽ほどきれいに調整できなかったが、それっぽい！　感動！

しかしここで終わっては何の新規性もない。くやしい。

他の再帰関数も聴きたい！！

**「竹内関数がいけるなら他の関数もいけるのでは？」**と思った。

再帰と聞いて思いついたのは

• アッカーマン関数
• フィボナッチ数列
• くりかえし自乗法
• 深さ優先探索
• 漸化式

など。そこどえ音楽にするために以下の条件を与えた。

1. 引数が3つあること
2. 引数のとりうる値の範囲が88以下であること

条件1は先ほどのたらいまわし関数と同様に3和音にしたいからで、条件2はピアノの鍵盤の数以上は対応付けが面倒だったからだ。（いや剰余使えばいくらでもできるがご愛嬌ということで）

というわけで良い感じそうなやつを作ってみた。

Tak関数

（急にニッチなやつ…。）

wikipediaによれば竹内関数を勘違いして生まれた関数のようだ。

ジョン・マッカーシーは竹内関数を記憶違いで$z$ を返すように変更し、これがTak関数として広まった。以下がその定義である。

{\displaystyle {\rm {Tak}}(x,y,z)={\begin{cases}z&{\mbox{ if }}x\leq y\{\rm {Tak}}({\rm {Tak}}(x-1,y,z),{\rm {Tak}}(y-1,z,x),{\rm {Tak}}(z-1,x,y))&{\mbox{ otherwise. }}\\end{cases}}}

>
> 計算量はずっと少ない（たとえば tarai(12, 6, 0) では 12,604,860 回 tarai が呼ばれるのに対し、 tak(12, 6, 0) では tak は 63,608 回しか呼ばれない）。

実装例は以下。

```python
def tak(x, y, z):
    """takはtaraiの return y を z としたもの
    """
    if x <= y:
        return z  # ここがtaraiと異なる
    else:
        return tak(tak(x - 1, y, z),
                   tak(y - 1, z, x),
                   tak(z - 1, x, y))

音楽は以下（クリックで再生）

なんとなく違った趣が感じられる。

3変数アッカーマン関数

普通のアッカーマン関数

アッカーマン関数は、**とんでもなく大きな数字（巨大数）がつくれることで有名？**だ。定義は以下。

{\displaystyle \operatorname {Ack} (m,n)={\begin{cases}n+1,&{\text{ if }}m=0\\\operatorname {Ack} (m-1,1),&{\text{ if }}n=0\\\operatorname {Ack} (m-1,\operatorname {Ack} (m,n-1)),&{\text{ otherwise}}\\\end{cases}}}

少し脱線するが、値の表も見てみよう。

m\n	0	1	2	3	4
0	1	2	3	4	5
1	2	3	4	5	6
2	3	5	7	9	11
3	5	13	29	61	125
4	13	65533	$2^{65536} − 3$	${\displaystyle {2^{2^{65536}}}-3}$	A(3, A(4, 3)) = $2^{2^{2^{65536}}} − 3$
5	65533	${\displaystyle {\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3 \\ 65536{\text{ twos}}\end{matrix}}}$	A(4, A(5, 1))	A(4, A(5, 2))	A(4, A(5, 3))

なんと$Ack(4, 2)$の時点で19,729ケタもあり、途中からは一般的な記法では数式を表現できなくなっている。

閑話休題。こんなおもしろい関数だが引数が二つしかない…！ でも使いたい！

多変数

意地になって調べてみると、多変数versionも提案されている。（多変数アッカーマン関数）

多変数アッカーマン関数 A(x1,x2,…,xn)A(x1,x2,…,xn) は、2007年にたろうが考案し、ふぃっしゅっしゅ(2013)に紹介された。2変数の時にはアッカーマン関数と同じで、3変数以上になると配列表記と同じ程度の増加率となる多重帰納関数である。

3変数の場合を書き下すと以下のようにかける。

{\displaystyle \operatorname {Ack} (l, m,n)=
{\begin{cases}
n+1,&{\text{ if }}m=n=0\\
\operatorname {Ack} (l, m-1,1),&{\text{ if }}n=0\\
\operatorname {Ack} (l-1, n, n),&{\text{ if }}m=0\\
\operatorname {Ack} (l, m-1, \operatorname {Ack} (l, m,n-1)),&{\text{otherwise}}\\
\end{cases}}}

あまりに数字が大きくなるのがはやいので、$Ack(1,1,1)$を鳴らしてみた。ただそれでも最大値は61、再帰回数2440回あるので、とんでもない関数だ。

実装例

def ack(l, m, n):
    """アッカーマン関数の3変数版
    """
    if l == 0 and m == 0:
        return n+1
    elif n == 0:
        return ack(l, m-1, 1)
    elif m == 0:
        return ack(l-1, n, n)
    else:
        return ack(l, m-1, ack(l, m, n-1))

動画（クリックで再生）

聴いてみるとわかるが、xとyがほとんど変化しない。xとyが0または1にしかならないので、やや単調な音楽になっているものの、途中に急にリズムが変わったりして楽しい。

まとめ

再帰関数で音楽を奏でてみました。音楽は素人ですが音が鳴ると楽しいですね！この記事では思いついた関数を3つだけ試してみましたが、
「探索アルゴリズムで音を鳴らしたらどうなるの？」
「こうすればもっと良く聞こえるんじゃないの？」
などは自分でやって報告してほしいです！私もやったんだからさ

何かお気づきの点がございましたら、コメントで教えてもらえると喜びます。

参考：クロージャを用いた実装

Global変数を用いずに再帰呼び出し回数を数える方法としてクロージャを使うものがある。再帰関数をある関数の中で定義することで、呼び出し回数をglobalではなくnonlocalにできる。以下は例として呼び出し回数をカウントする関数だ。

def count_tarai(x, y, z) -> int:
    count = 0

    def tarai(x, y, z):
        nonlocal count
        count += 1
        if x <= y:
            return y
        else:
            return tarai(tarai(x-1, y, z),
                         tarai(y-1, z, x),
                         tarai(z-1, x, y))

    tarai(x, y, z)
    return count

詳しくはクロージャとかnonlocalとかでググってください。

記事ではクロージャやnonlocalの説明を入れる気はなかったので、雑だが理解しやすい実装をのせました。グローバル変数の実装例が不評だったら、差し替えるのでコメントいただけると幸いです。