Avez-vous déjà «écouté» des ** «fonctions récursives»? ** **

Je pense que c'est rare de l'avoir entendu, alors appréciez un peu la musique.

Fait de la musique

Cliquez sur l'image ** ci-dessous pour ouvrir YouTube **. Les miniatures sont les mêmes, mais un lien différent s'ouvre correctement.

Fonction Taraimawashi

Fonction Tak

Fonction Ackermann à 3 variables

Le début de l'histoire

En 2011, un article "Génération de musique avec fonction Takeuchi" a été publié pour faire de la musique avec fonction Takeuchi (fonction Taramawashi). Ce qui suit est la vidéo, et vous pouvez voir que la fonction récursive fait de la bonne musique.

↑ Vidéo originale

Fonction Takeuchi (fonction Taramawashi)

C'est une fonction récursive comme la suivante.

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

En premier lieu, si vous demandez "qu'est-ce qu'une fonction récursive?", Voir l'article de Kencho "Quel genre de monde se développera lorsque vous apprendrez les fonctions récursives". Je pense que c'est parfait.

Comme vous pouvez le voir dans la définition, la fonction Takeuchi appelle le processus de manière récursive, mais l'argument $ z $ n'est pas utilisé dans l'instruction if, donc c'est très inutile. Par exemple, si vous appelez $ Tarai (10, 5, 0) $, vous aurez 343 073 appels récursifs. La raison pour laquelle cela est lié à la musique est citée ci-dessous.

J'ai écrit un programme pour découvrir comment les arguments de cet appel de fonction changent, et dans le cas de Tarai (10,5,0), chacun des trois arguments est de 0 à 10 (x est de -1 à ~). En changeant petit à petit entre 10), il y a un comportement selon lequel deux valeurs sont fixées et une valeur descend, ce qui rappelle quelque peu la progression d'accords des trois accords de la musique. C'est un. 　 Dans ce cas, je l'ai écouté comme un son. Chaque fois que la fonction Tarai est appelée, les arguments x, y et z sont assignés au son comme 0 = mi, 1 = fa, 2 = so, ..., et sonnent comme 3 accords. Comme c'est un gros problème, la source sonore automatique Arpeggio le rend minimal. Je suis. Je pense que c'est un peu intéressant car il y a un changement de tension pour ce genre de musique générée automatiquement.

Ingéniosité pour faire de la musique

** Il semble que j'ai fait de la musique en faisant correspondre le numéro de l'argument de la fonction récursive à Doremi **. Consultez le tableau ci-dessous.

Nombres	-1	0	1	2	3	4	5	6	7	8	9	10
du son	Les	Mi	FA	Alors	La	Shi	Faire	Les	Mi	FA	Alors	La

Selon le proposant

--Utiliser uniquement les touches blanches (ne pas utiliser #)

La valeur minimale (-1) a été définie sur l'échelle dorienne. --J'ai conçu le tempo et le ton

J'ai donc décidé d'imiter cela. Jusqu'à ce point, le contenu existant.

Essayez de mettre en œuvre

C'est pourquoi ** je l'ai essayé **.

Je ne connais pas le MIDI, j'ai donc utilisé le moteur de jeu rétro Python Pyxel. Le code ci-dessous (légèrement long). De plus, cette implémentation utilise la † evil Global variable †, donc vérifiez [Référence: Implémentation utilisant la fermeture](#Reference: Implémentation utilisant la fermeture) pour un meilleur exemple d'implémentation.

import pyxel
import sys
sys.setrecursionlimit(10_000_000) #Augmenter la limite supérieure de récurrence

#† Variables globales maléfiques †
cnt = 0  #Nombre d'appels récursifs

# -1:Les, 0:Mi, ....Correspondre à
note = ["C3", "D3", "E3", "F3", "G3",
        "A4", "B4", "C4", "D4", "E4", "F4", "G4",
        "B3"]  # -Son correspondant à 1

#Argument de la fonction Takeuchi comme note
melody_x = ""
melody_y = ""
melody_z = ""

#Gardez les arguments pour dessiner
xs = []
ys = []
zs = []


def tarai(x, y, z):
    """tarai(10, 5, 0)Est-Changer de 1 à 10
    """
    global cnt
    global melody_x, melody_y, melody_z
    global xs, ys, zs
    
    cnt += 1
    if cnt >= 500:
        raise StopIteration("Fin de l'appel récursif -")

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

    #Traitement récursif
    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):
    """Définir la musique le long d'une fonction
    """
    global melody_x, melody_y, melody_z
    SPEED = 20  #120 pour une note par seconde,120 par seconde/SPEED fois

    #Enregistrez jusqu'à 500 récurrences
    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_Nom illégal: tarai, tak,Veuillez spécifier l'un des ack")
    except ValueError as e:
        print(e)
    except StopIteration as e:
        print(e)

    #Définissez la musique en fonction de chaque 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():
    """Dessinez le clavier
    """
    _width = pyxel.width//14  #Parce qu'il y a 14 clés
    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)
    
    # (Arguments de la fonction Takeuchi+2)Correspond à l'emplacement du clavier
    #Colorez les touches que vous jouez
    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)

    #Dessinez le clavier
    for i in range(14):
        #Clé blanche
        pyxel.rectb(x=2+_width*i, y=20, w=_width,
                    h=60, col=pyxel.COLOR_BLACK)
        #Clé noire
        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) #jouer de la musique
    pyxel.run(update, draw)

J'ai entendu un son comme celui-ci. (Republiez le premier lien de l'article. Cliquez pour lire).

** Je ne pourrais pas l'ajuster aussi bien que la musique du proposeur, mais ça y ressemble! Impressionné! ** **

Mais terminer ici n'a rien de nouveau. Je suis malade.

Je veux aussi entendre d'autres fonctions récursives! !!

** J'ai pensé: "Si la fonction Takeuchi peut être utilisée, d'autres fonctions peuvent-elles être utilisées?" **.

Ce qui m'est venu à l'esprit quand j'ai entendu dire que c'était récursif

Fonction d'Ackerman --Séquence de numéros Fibonatch
Méthode autopropulsée répétée
Recherche de priorité en profondeur
Formule progressive

Tel. Les conditions suivantes ont été données pour en faire de la musique.

** Doit avoir 3 arguments **
** La plage de valeurs possibles pour l'argument est de 88 ou moins **

La condition 1 est parce que nous voulons faire 3 accords comme la fonction Taramawashi plus tôt, et la condition 2 est parce qu'il est difficile d'associer plus que le nombre de touches de piano. (Non, vous pouvez utiliser le surplus autant que vous le souhaitez, mais c'est mignon)

C'est pourquoi j'ai créé un gars qui a l'air bien.

Fonction Tak

(Soudain une niche ...)

Selon wikipedia, cela semble être une fonction qui a été créée par une mauvaise compréhension de la fonction Takeuchi.

[John McCarthy](https://ja.wikipedia.org/wiki/John McCarthy) a modifié la fonction Takeuchi pour renvoyer $ z $ en raison d'une erreur de mémoire, qui est devenue populaire sous le nom de ** fonction Tak **. .. Voici la définition.

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

>
 > Beaucoup moins de calculs (par exemple, tarai (12, 6, 0) appelle tarai 12 604 860 fois, tandis que tak (12, 6, 0) appelle seulement 63 608 fois).

 L'exemple de mise en œuvre est le suivant.

```python
def tak(x, y, z):
    """tak est le retour de tarai y comme z
    """
    if x <= y:
        return z  #C'est différent du tarai
    else:
        return tak(tak(x - 1, y, z),
                   tak(y - 1, z, x),
                   tak(z - 1, x, y))

La musique est ci-dessous (cliquez pour jouer)

D'une certaine manière, je ressens un ** goût différent **.

Fonction Ackermann à 3 variables

Fonction Ackerman ordinaire

La fonction Ackermann est-elle réputée pour sa capacité à créer des nombres ridiculement grands (nombres énormes)? **. La définition est la suivante.

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

Jetons un coup d'œil au tableau des valeurs, même s'il s'écarte un peu.

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

Au moment de $ Ack (4, 2) $, il y a 19 729 chiffres, et à partir du milieu, il n'est pas possible d'exprimer des formules mathématiques en notation générale.

Pause de conversation tranquille. C'est une fonction intéressante, mais elle n'a que deux arguments **…! Mais je veux l'utiliser!

Multivariable

Lorsque j'ai obstinément enquêté, ** une version multivariée a également été proposée **. ([Fonction Ackerman multivariée]([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 / fonction Ackermann multivariée))))

** Fonction Ackermann multivariée ** A (x1, x2,…, xn) A (x1, x2,…, xn) a été conçue par Taro en 2007 et introduite dans Fishshu (2013). C'était. Lorsqu'il y a deux variables, c'est la même chose que la [fonction Ackerman](https://googology.wikia.org/ja/wiki/Ackerman function), et quand il y a trois variables ou plus, c'est la notation Array. C'est une [fonction de régression multiple](https://googology.wikia.org/ja/wiki/multiple regression function) qui a le même taux d'augmentation que la notation ja / wiki / array).

Si vous notez le cas de 3 variables, il sera multiplié comme suit.

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

C'est trop rapide pour que les nombres deviennent trop gros, alors j'ai joué à $ Ack (1,1,1) $. Cependant, la valeur maximale est de 61 et le nombre de récidives est de 2440, c'est donc une fonction ridicule.

Exemple d'implémentation

def ack(l, m, n):
    """Version à 3 variables de la fonction Ackerman
    """
    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))

Vidéo (cliquez pour lire)

Comme vous pouvez le voir en écoutant, x et y changent à peine. Puisque x et y ne valent que 0 ou 1, c'est un peu de la musique monotone, mais c'est amusant car le rythme change soudainement au milieu. ** **

Résumé

** J'ai joué de la musique avec une fonction récursive. ** La musique est un amateur, mais c'est amusant d'entendre le son! Dans cet article, je n'ai essayé que trois fonctions que j'ai proposées, "Que se passe-t-il si vous émettez un son avec l'algorithme de recherche?" "Ça ne sonne pas mieux ainsi?" Etc. ** Je veux que vous le fassiez vous-même et que vous le signaliez! Je l'ai fait aussi **

Si vous avez des questions, veuillez nous le faire savoir dans les commentaires.

Référence: mise en œuvre par fermeture

Il existe une méthode qui utilise la fermeture comme méthode de comptage du nombre d'appels récursifs sans utiliser la variable Global. En définissant une fonction récursive dans une fonction, le nombre d'appels peut être défini sur «non local» au lieu de «global». Voici une fonction qui compte le nombre d'appels à titre d'exemple.

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

Pour plus d'informations, veuillez google avec fermeture ou "non local".

Je n'avais pas l'intention d'inclure une description des fermetures ou «non locales» dans l'article, donc j'ai mis une implémentation grossière mais facile à comprendre. Si l'exemple d'implémentation de la variable globale est impopulaire, je le remplacerai, donc j'apprécierais que vous puissiez commenter.

Musique jouée par des fonctions récursives

Fait de la musique

Fonction Taraimawashi

Fonction Tak

Fonction Ackermann à 3 variables

Le début de l'histoire

Fonction Takeuchi (fonction Taramawashi)

Ingéniosité pour faire de la musique

Essayez de mettre en œuvre

Je veux aussi entendre d'autres fonctions récursives! !!

Fonction Tak

Fonction Ackermann à 3 variables

Fonction Ackerman ordinaire

Multivariable

Résumé

Référence: mise en œuvre par fermeture