Music played by recursive functions

Have you ever "listened" to ** "recursive functions"? ** **

I think it's rare to have heard it, so please enjoy the music a little.

Made music

Click the ** image below to open youtube **. The thumbnails are the same, but a different link opens up properly.

Taraimawashi function

tarai

Tak function

tak

3-variable Ackermann function

tak

The beginning of the story

In 2011, an article "Music generation with Takuchi function" was published to make music with Takuchi function. Below is the video, where you can see that the recursive function makes good music.

tak ↑ Original video

Takeuchi function (Taramawashi function)

The recursive function is as follows.

\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}

In the first place, if you are asking "what is a recursive function?", See Kencho's article "What kind of world will expand when you learn recursive functions". I think it's perfect if you let it through.

As you can see from the definition, the Takeuchi function calls the process recursively, but the argument $ z $ is not used in the if statement, so it is very wasteful. For example, if you call $ Tarai (10, 5, 0) $, the recursive call will be 343,073 times. The reason why this is related to music is quoted below.

I wrote a program to find out how the arguments of this function call change, and in the case of Tarai (10,5,0), each of the three arguments is 0 to 10 (x is -1 to ~). While changing little by little between 10), there is a behavior that two values are fixed and one value goes down, which is somewhat reminiscent of the chord progression of the three chords of music. It is one. 　 In that case, I actually listened to it as a sound. Every time the Tarai function is called, the arguments x, y, and z are assigned to sounds like 0 = mi, 1 = fa, 2 = so, ..., and sounded as 3 chords. Since it's a big deal, the automatic sound source Arpeggio makes it look minimal. I am. I think it's a little interesting for this kind of automatically generated music because there is a change in tension.

Ingenuity to make music

** It seems that I made music by making the number of the argument of the recursive function correspond to Doremi **. See the table below.

Numbers -1 0 1 2 3 4 5 6 7 8 9 10
sound Re Mi Fa So La Shi Do Re Mi Fa So La

According to the proposer

--Use only white keys (do not use #) --The minimum value (-1) was set to the durian scale. --The tempo and tone have been devised

So I decided to imitate this. Up to this point, the existing contents.

Try to implement

That's why ** I actually tried it **.

I don't know MIDI, so I used the Python retro game engine Pyxel. The code below (slightly long). Also, this implementation uses the † evil Global variable †, so check [Reference: Implementation using closures](#Reference: Implementation using closures) for a better implementation example.

import pyxel
import sys
sys.setrecursionlimit(10_000_000) #Raise the upper limit of recursion

#† Evil global variables †
cnt = 0  #Recursive call count

# -1:Re, 0:Mi, ....Correspond to
note = ["C3", "D3", "E3", "F3", "G3",
        "A4", "B4", "C4", "D4", "E4", "F4", "G4",
        "B3"]  # -Sound corresponding to 1

#Takeuchi function argument as a musical note
melody_x = ""
melody_y = ""
melody_z = ""

#Keep arguments for drawing
xs = []
ys = []
zs = []


def tarai(x, y, z):
    """tarai(10, 5, 0)Is-Change from 1 to 10
    """
    global cnt
    global melody_x, melody_y, melody_z
    global xs, ys, zs
    
    cnt += 1
    if cnt >= 500:
        raise StopIteration("End of recursive call ―")

    #Hold arguments
    melody_x += note[x]
    melody_y += note[y]
    melody_z += note[z]
    xs.append(x)
    ys.append(y)
    zs.append(z)

    #Recursive processing
    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):
    """Define music along a function
    """
    global melody_x, melody_y, melody_z
    SPEED = 20  #120 for one note per second,120 per second/SPEED times

    #Record up to 500 recursion
    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_Illegal name: tarai, tak,Please specify one of ack")
    except ValueError as e:
        print(e)
    except StopIteration as e:
        print(e)

    #Define music according to each argument
    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():
    """Draw the keyboard
    """
    _width = pyxel.width//14  #Because there are 14 keys
    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)
    
    # (Takeuchi function arguments+2)Corresponds to the location of the keyboard
    #Color the keyboard you play
    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)

    #Draw the keyboard
    for i in range(14):
        #White key
        pyxel.rectb(x=2+_width*i, y=20, w=_width,
                    h=60, col=pyxel.COLOR_BLACK)
        #Black key
        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) #play music
    pyxel.run(update, draw)

I heard a sound like this. (Repost the first link in the article. Click to play).

tarai

** I couldn't adjust it as cleanly as the proposer's music, but it looks like it! Impressed! ** **

But ending here is nothing new. I'm sick.

I want to hear other recursive functions too! !!

** I thought, "If the Takeuchi function can be used, other functions can be used?" **.

What came to my mind when I heard that it was recursion

--Ackermann function --Fibonacci sequence --Repeated self-multiplication method --Depth-first search --Recurrence formula

Such. The following conditions were given in order to make it music.

  1. ** Must have 3 arguments **
  2. ** The range of possible values for the argument is 88 or less **

Condition 1 is because we want to make triads like the previous Taramawashi function, and condition 2 is because it is troublesome to associate more than the number of piano keys. (No, you can use the surplus as much as you want, but it's cute)

That's why I made a guy that looks good.

Tak function

(Suddenly a niche guy ...)

According to wikipedia, it seems that ** a function was created by misunderstanding the Takeuchi function **.

[John McCarthy](https://ja.wikipedia.org/wiki/John McCarthy) changed the Takeuchi function to return $ z $ due to misremembering, which became popular as the ** Tak function **. .. The following is the definition.

{\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}}}

>
 > The complexity is much smaller (for example, tarai (12, 6, 0) calls tarai 12,604,860 times, while tak (12, 6, 0) calls tak only 63,608 times).

 The implementation example is as follows.

```python
def tak(x, y, z):
    """tak is tarai's return y as z
    """
    if x <= y:
        return z  #This is different from tarai
    else:
        return tak(tak(x - 1, y, z),
                   tak(y - 1, z, x),
                   tak(z - 1, x, y))

Music is below (click to play)

tarai Somehow I feel ** different taste **.

3-variable Ackermann function

Ordinary Ackermann function

Is the Ackermann function famous for creating ridiculously large numbers (large numbers)? **. The definition is as follows.

{\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}}}

Let's derail a little, but let's also look at the table of values.

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))

At the time of $ Ack (4, 2) $, there are 19,729 digits, and from the middle, it is not possible to express mathematical formulas with general notation.

Quiet talk break. This is an interesting function, but it has only two arguments **…! But I want to use it!

Multivariable

When I stubbornly investigated, ** a multivariable version was also proposed **. ([Multivariable Ackermann Function]([https://googology.wikia.org/ja/wiki/%E5%A4%9A%E5%A4%89%E6%95%B0%E3%82%A2%E3%] 83% 83% E3% 82% AB% E3% 83% BC% E3% 83% 9E% E3% 83% B3% E9% 96% A2% E6% 95% B0](https://googology.wikia.org) / ja / wiki / multivariable Ackermann function))))

** Multivariable Ackermann function ** A (x1, x2,…, xn) A (x1, x2,…, xn) was devised by Taro in 2007 and introduced in Fishshu (2013). It was. It is the same as [Ackermann function](https://googology.wikia.org/ja/wiki/Ackermann function) when it is 2 variables, and Array notation when it is 3 variables or more. It is a [multiple regression function](https://googology.wikia.org/ja/wiki/multiple regression function) that has the same rate of increase as ja / wiki / array notation).

If you write down the case of 3 variables, it will be multiplied as follows.

{\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}}}

It's too fast for the numbers to get too big, so I played $ Ack (1,1,1) $. However, the maximum value is 61 and the number of recursion is 2440, so it is a ridiculous function.

Implementation example

def ack(l, m, n):
    """3-variable version of the Ackermann function
    """
    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))

Video (click to play)

tarai

As you can see by listening, x and y hardly change. Since x and y are only 0 or 1, it's a little monotonous music, but it's fun because the rhythm suddenly changes in the middle. ** **

Summary

** I played music with a recursive function. ** Music is an amateur, but it's fun to hear the sound! In this article I've tried only three functions I came up with, "What happens if you make a sound with a search algorithm?" "Doesn't it sound better this way?" Etc. ** I want you to do it yourself and report it! I did it too **

If you have any questions, please let us know in the comments.

Reference: Implementation using closures

There is a method that uses closures as a method of counting the number of recursive calls without using Global variables. By defining a recursive function inside a function, the number of calls can be set to nonlocal instead of global. The following is a function that counts the number of calls as an example.

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

For more information, please google for closures or nonlocal.

I didn't intend to include closures or nonlocal descriptions in the article, so I've included a crude but easy-to-understand implementation. If the implementation example of global variables is unpopular, I will replace it, so I would appreciate it if you could comment.

Recommended Posts

Music played by recursive functions
Visualize activation functions side by side
Memorandum on Memoization of recursive functions