Langage Recurcif

Le calcul récursif

  1. Notation post-fixée
  2. Notation prés-fixée

 

1) Le calcul récursif

La récurrence primitive est la répétition d'un calcul réutilisant des résultats intermédiaires, un nombre de fois fixées par des données résultant de calcul intermédiaire. Cela correspond à l'utilisation dans un langage de programmation courante aux seules boucles for. En s'inspirant des travaux de Herbrand, on peut représenter le détail du calcul récursif primitif par un arbre, et factoriser cet arbre en une représentation moins redondante, définissant ainsi un langage qui est une extension de l'univers de Herbrand d'ordre 1.

Cette extension est obtenue en ajoutant un meta opérateur ®, appelé itérateur, qui permettra de construire la formule développée selon les itérations, c'est à dire la formule sans le meta opérateur ®. On peut choisire une notation post-fixée ou prés-fixée si l'on souhait que l'itérateur soit enfant ou parent de la fonction itérée.

L'arbre peut alors être développé d'une autre façon, dite selon les fonctions, en remplaçant toutes les fonction, noeuds de l'arbre, par des sous-arbres qui les calculent, de tel sorte que chaque noeuds de l'arbre résultant est, soit la fonction S ou soit un itérateur ®i.

2) Notation post-fixée

L'itérateur a une particularité graphique, il pointe sur une fonction parente, un noeud de la formule, c'est à dire un noeud de l'arbre, et désigne donc un sous arbre. On représente ce lien dans les formules par un souligné. L'itérateur possède deux arguments n et x correspondant au nombre n d'itération et à la valeur initiale x. L'itérateur ®(n,x) est, en plus, associé à un index £ qui vaudra {n,n-1,n-2...,3,2,1,0}dans les différentes étapes de développement selon les itérations, de la formule. Afin que le nombre d'itération correspondes à n, on fixe l'arrêt du développement lorsque n=1.

f(y,£,®(n,x)) = f(y,n,f(y,£,®(n-1,x)))
f(y,£,®(1,x)) = f(y,1,x)

Lorsque n = 0, cela signifie qu'il y a zéro itération. L''itérateur ®(n,x) étant à l'intérieur de la fonction itéré, on adopte la défintion d'absorbtion, à savoir que lorsque l'itérateur ®(0,x) est présent, celui-ci remplace l'arbre qu'il pointe par la valeur x :

f(y,£,®(0,x)) = x

 

Algorithme mathématique
Algorithme avec itérateur ®,£
Algorithme développé
Add(x,0) = x
Add(x,y+1) = S(Add(x,y))
S(®(y+1,x))
S(S(S... S(x)...))   S apparaît  y+1 fois
f(z,0) = x
f(z,n+1) = h(z, n, f(z,n))
h(z,£,®(n+1,x))
h(z,n+1,h(z,n,h(z,n-1...h(z,1,x)...))    n+1 fois

Add(x,y) = S(®(y,x)) = S(S(®(y-1,x))) = S(S(S... S(x)...))    S apparait y fois
Add(x,3) = S(®(3,x)) = S(S(®(2,x))) = S(S(S(®(1,x))) = S(S(S(x)))    S apparait 3 fois

f(z,n) = h(z,£,®(n,x)) = h(z,n,h(z,n-1,h(z,n-2...h(z,1,x)...))    h apparait n fois
f(z,3) = h(z,£,®(3,x)) = h(z,3,h(z,£,®(2,x))) = h(z,3,h(z,2,h(z,£,®(1,x)))) = h(z,3,h(z,2,h(z,1,x)))   h apparait 3 fois

3) Notation prés-fixée

L'itérateur ®(n,x,f(...)) possède deux premiers arguments n et x correspondant au nombre n d'itération et à la valeur initiale x, et un dernier argument désignant la fonction itéré f(...). L'itérateur ®(n,x,f(...)) est en plus associé à deux variables £ et µ, qui peuvent être placées à plusieurs feuilles de l'arbre itéré f(...), et qui vaudront pour £, {n,n-1,n-2...,3,2,1,0}, et pour µ, le résultat de la n-ième itération, au cours du développement selon les itérations, de la formule :

®(f(y,£,µ),n,x)) = f(y,n,®(f(y,£,µ),n-1,x)))
®(f(y,£,µ),1,x)) = f(y,1,®(f(y,£,µ),0,x))) = f(y,1,x)
®(f(y,£,µ),0,x)) = x

Cela nécessite d'avantage de symboles mais il n'est plus nécessaire de préciser un lien graphique. C'est pourquoi nous choisirons la notation prés-fixée.

Algorithme mathématique
Algorithme avec itérateur ®,£
Algorithme développé
Add(x,0) = x
Add(x,y+1) = S(Add(x,y))
®(y+1,x,S(µ))
S(S(S... S(x)...))    S apparaît  y+1 fois
f(z,0) = x
f(z,n+1) = h(z, n, f(z,n))
®(n+1,x,h(z,£,µ))
h(z,n+1,h(z,n,h(z,n-1...h(z,0,x)...))    n+1 fois

Add(x,y) = ®(y,x,S(µ)) = S(®(y-1,x,S(µ))) = S(S(S... S(x)...))    S apparait y fois
Add(x,3) = ®(3,x,S(µ)) = S(®(2,x,S(µ))) = S(S(®(1,x,S(µ)))) = S(S(S(x)))    S apparait 3 fois

f(z,n) = ®(n,x,h(z,£,µ)) = h(z,n,h(z,n-1,h(z,n-2...h(z,1,x)...))    h apparait n fois
f(z,3) = ®(3,x,h(z,£,µ)) = h(z,3,®(n-1,x,h(z,£,µ))) = h(z,3,h(z,2,®(1,x,h(z,£,µ)))) = h(z,3,h(z,2,h(z,1,x)))

Le modèle de la fonction itéré est colorié en rose. Le méta opérateur itération est colorié en vert.

Quand il y a plusieurs itérations emboitées, on utilise autant d'itérateurs ®1, ®2, ®3..., avec leurs index associés £1, £2, £3..., et mémoire tampon µ1, µ2, µ3.... Et nous sommes toujours assurés que notre algorithme de développement d'itération s'achève en un temps fini.

Par exemple, la multiplication est définie récursivement par Mult(x,y) = ®(y,0,Add(x,µ)) à partir de l'addition qui est elle-même définie récursivement par Add(x,y) = ®(y,x,S(µ)), et donc en numérotant ces deux itérateurs afin de les différencier, la multiplication se définie récursivement par :

Mult(x,y) = ®1(y,0,®2(µ1,x,S(µ2)))

®2(µ1,x,S(µ2)) corespond à l'adition de la mémoire tampon µ1 et de la donnée x. Donc µ1 et x peuvent être permutés, et comme x et y peuvent être permutés, nous avons la formule d'avantage mémotechnique suivante :

Mult(x,y) = ®1(x,0,®2(y,µ1,S(µ2)))