billaj a écrit :zpalm a écrit :Sur la HP-41 la pile de retour des sous-programmes a une profondeur de 6, ce qui veut dire que l’on ne peut revenir que 6 niveaux en arrière. Donc ça ne devrait pas marcher pour n <45!!
En fait on est sauvé car pour tout n <=90 la valeur est 91, donc lorsque l’on calcule par ex. M(5) on dépasse le nombre de niveaux autorisés, on ne revient donc pas au début des appels comme on peut le voir en passant en mode programme : le programme s’est arrêté sur le dernier RTN du programme. Mais la 41 affiche la bonne valeur : 91.
Autrement dit :
Récursivité terminale FTW !
Je m'auto-cite pour annuler cette belle connerie que j'ai écrite ici : l'algorithme de la fonction M, nativement, n'est
pas récursif terminal !
La différence est pourtant simple : une fonction récursive terminale renvoie en toute dernière opération le résultat de l'appel récursif, tandis qu'une non terminale y applique ensuite d'autres traitements.
La fonction M est donc non terminale...elle serait terminale si pour n>100 on renvoyait M(n+11). Mais on renvoie M(M(n+11))...on a donc besoin du pointeur d'exécution dans le niveau actuel du programme pour, après avoir évalué M(n+11), évaluer M(ce nombre)...
...en fait, c'est assez intéressant, à chaque étape on enchaîne un appel non terminal M(n+11) auquel on applique l'appel terminal M(M(n+11)) !
Ceci revient à dire plus simplement qu'on a deux appels successifs, l'entrée du second étant la sortie du premier...
En termes d'implémentation, la différence récursivité non terminale/terminale devient ceci :
-Dans un cas, comme on post-traite le retour de l'appel récursif, on a besoin de garder en mémoire l'état de la fonction appelante : pointeur d'exécution, variables locales (en tout cas, celles encore utilisées par la suite)
-Dans l'autre, comme on ne fait que renvoyer tel quel le résultat de l'appel récursif (situation plus ou moins facile à détecter), on n'a besoin de rien conserver de la fonction appelante, pas même le pointeur d'exécution. Un interpréteur/compilateur malin tient compte de cette situation pour optimiser la gestion de la mémoire.
Ceci se traduit de deux façons différentes si on "itératifie"/"dérécursifie" l'algorithme :
-Dans un cas, il est nécessaire de garder des informations sur les itérations précédentes. Compteur ou autre information "synthétique" dans le meilleur des cas, pile de variables et d'ex-paramètres dans le pire (avec boucle/empilage pour les appels récursifs puis 2ème boucle inverse/dépilage pour le post-traitement)
-Dans l'autre, il ne va s'agir que de la réaffectation/écrasement de variables locales (les ex-paramètres) et d'un Goto.
Dans le cas de la fonction de McCarthy, comment cela se traduit-il ? On n'a pas de variable locale, la seule chose qu'on a à stocker lors de la première récursion (non terminale) est l'équivalent du pointeur de pile, on n'a même pas besoin de sauvegarder n. On fait ensuite un appel de la même fonction donc on a juste besoin de "savoir" dans laquelle des deux itérations on se trouve. Et comme pour ce deuxième appel on a simplement en entrée le résultat brut du premier appel, on n'a au final pas de traitement différencié entre les deux appels ni entre ceux-ci et ceux imbriqués et donc un simple compteur suffit pour dérécursifier la fonction ! La non-terminalité de l'ensemble se retrouvant dans le besoin d'avoir ce compteur au lieu d'un simple goto.
J'espère ne pas avoir écrit de grosse connerie...très intéressante cette fonction en tout cas !
Autres réflexions sur le thème de la récursion :
Un truc assez intéressant à noter est que sur nos pockets où les variables sont en général statiques, la récursion dans un cas où on a des variables locales à stocker nous oblige malgré tout à gérer nous-même une pseudo-pile (sous forme de tableau), les pointeurs d'instruction en moins.
Un deuxième truc intéressant est de remarquer que ce modèle est justement celui selon lequel nos ordinateurs sont conçus et implémentent les appels récursifs. Dérécursifier revient donc à faire une partie du boulot du compilateur, en l'optimisant et en remplaçant la gestion de pile native du CPU par la nôtre.
Quand Chuck Norris joue à Nintendogs, il a automatiquement armes et munitions infinies.
Chuck Norris peut revenir en arrière dans Super Mario Land.
Chuck Norris utilise exclusiment des calculatrices Texas Instruments.