Salut tout le monde.
Lorsqu’une fonction ou une procédure peut
s’appeler elle-même , on dit que c’est de la
récursivité directe .
On peut également réaliser
la récursivité croisée , c.à.d. que plusieurs procédures ou fonctions peuvent s’appeler mutuellement.
NOTION DE RECURSIVITELa récursivité est une notion générale que l’on rencontre dans bien d’autres domaines que la programmation.
On dit qu’il y a récursivité lorsque la définition d’un objet fait apparaître l’objet lui-même.
C’est ainsi que la notion d’instruction devait être définie d’une manière récursive.
Plus précisément, une instruction peut être soit une instruction simple, soit une instruction composée.
Or, une instruction composée contient à son tour des instructions qui sont soit des instructions simples soit des instructions composées qui à leur tour ....
Pour mieux exprimer mon idée sur la récursivité, je vais prendre le cas archi connu de la fonction factorielle.
Bien entendu, Panoramic ne permet pas encore la définition des fonctions (ça arrivera tôt ou tard le moment venu).
Ce qui suit peut éclaircir les choses.
La fonction factorielle peut se définir ainsi :
Fac(1) = 1
Fac(n) = n * Fac(n-1) pour n > 1
La seconde ligne qui définit Fac(n) pour n > 1 comporte à son tour une référence à Fac. Il y a bien récursivité.
Bien entendu, une telle définition est cohérente et exploitable car en l’appliquant un
nombre fini de fois, elle permet d’aboutir à un résultat.
Par exemple, pour n = 3, on trouvera d’abord :
Fac(3) = 3 * Fac(2)
Puis, en appliquant à nouveau la définition :
Fac(3) = 3 * 2 * Fac(1)
Là, c’est la 1ère ligne de la définition qui intervient en arrêtant en quelque sorte le processus récursif et qui nous amène à :
Fac(3) = 3 * 2 * 1
Une définition apparemment voisine, telle que :
Fac(1) = 1
Fac(n) = (Fac(n+1)/n) pour n > 1
aurait par contre été inexploitable. Intuitivement, on comprend que cette définition ne se termine jamais.
Exemple de fonction recursive(Je suppose que la déclaration d’une fonction se fait par FNC …)
- Code:
-
FNC Fac(n)
if n = 1 then fac = 1 : else : fac = n * fac(n-1)
END_FNC
Notez que, au sein de notre fonction, le même symbole FAC désigne 2 choses différentes.
A gauche d’une affectation, il représente la
pseudo variable destinée à recevoir la valeur de la fonction ; dans ce cas, il ne peut être suivi de parenthèses.
A droite d’une affectation, par contre, il représente un appel de cette fonction ; dans ce cas, il doit absolument être suivi de parenthèses ente lesquelles on trouve les arguments effectifs.
Notez que ce problème ne se pose pas pour les procédures.
Pour bien mettre en évidence la manière dont se déroule l’exécution d’une telle fonction, ajoutons 2 instructions d’écriture et incorporons le tout dans un programme principal
- Code:
-
print "Voici le calcul de fac(3)"
print "resultat = " ;fac(3)
end
FNC fac(n)
print " *** entrée dans fac n = " ; n
if n = 1
fac = 1
else
fac = n * fac(n-1)
end_if
print " +++ Sortie de fac n = " ; n
END_FNC
Le resultat de ce programme devrait être ainsi
- Code:
-
Voici le calcul de fac(3)
*** entrée dans fac n = 3
*** entrée dans fac n = 2
*** entrée dans fac n = 1
+++ sortie de fac n = 1
+++ sortie de fac n = 2
+++ sortie de fac n = 3
resultat = 6
Les messages affichés montrent que l’on est entré à 3 reprises dans fac, sans en sortir.
Il y a eu
empilement des appels En même temps, il a été nécessaire de conserver les valeurs des variables internes de FAC
avant de procéder à un nouvel appel.L’empilement des appelsTout d’abord, le programme principal appelle FAC avec comme argument la valeur 3.
Lors de l’entrée dans FAC, il y a automatiquement une allocation de mémoire dynamique (dans la pile) pour les variables locales ; ici, ces dernières se réduisent à l’argument d’entrée N et à l’argument de retour que nous noterons FAC.
Notez bien que FAC s’est vu allouer une place, mais pas encore de valeur.
L’exécution de la fonction commence alors, provoquant l’affichage du message *** entrée dans fac n = 3
L’instruction IF suivante entraine alors l’amorce de l’exécution de l’affectation : fac = n * fac(n-1)
Celle-ci provoque un nouvel appel de fac, avec en argument la valeur 2.
En toute rigueur, fac a besoin d’un emplacement dynamique pour ranger la valeur de l’expression n-1.
On entre donc à nouveau dans les instructions de fac.
Il y a de nouveau allocation de mémoire dynamique pour les variables locales.
Il y a de nouveau affichage de la valeur de n puis appel de fac avec l’argument 1.
Cette 3ème fois, après affichage du message d’entrée, l’instruction suivante conduit à affecter la valeur 1 à fac.
Cette fois, l’exécution de la fonction se poursuit jusqu’au bout provoquant l’affichage du message :
+++ sortie de fac n = 1
Il y a retour dans la fonction appelante avec restitution du resultat (ici 1) et libération de l’espace associé aux variables internes.
On se retrouve donc dans fac dans l’instruction qui avait provoqué ce dernier appel, c.-à-d. :
FAC = n * FAC(n-1)
La valeur de fac(n-1) est maintenant calculée (elle vaut 1). Le produit par n peut être réalisé.
Là encore, la fonction s’exécute jusqu’au bout. Il y a affichage d’un message de sortie, libération de l’espace associé aux variables internes et retour dans fac au niveau du 1er appel, avec comme resultat la valeur 2. Cette valeur est alors multiplié par n (ici 3) et le resultat est rangé dans fac.
De nouveau la fonction fac s’exécute jusqu’au bout. Elle fournit le resultat 6 au programme principal qui l’affiche.
ON NE PEUT PARLER DE PROCEDURES OU FONCTIONS RECURSIVES SI CES DERNIERES NE FONT PAS APPELS A ELLES-MEME AU SEIN MEME DE ELLES-MEMECe n’est pas clair comme définition hein ?
Disons :
Une fonction (ou procédure) récursive est une fonction (ou procédure) qui peut s'appeler elle-même au cours de son exécution.Une fonction (ou procédure) récursive peut s’appeler elle-même à partir de plusieurs endroits différents à l’intérieur de elle-même !
Dans tous les cas, la fonction (ou procédure)
doit aller jusqu’au bout de sa définition c.à.d.
exécuter toutes les instructions qui suivent les appels et ce jusqu’au END_FNC (ou END_SUB)
Si ce que vous venez de lire, vous a un tout petit peu éclairé, je serais très content !
Accueil 
Calendrier
sur mon prg, autant j'aime bien voir une idée. C'est affreux! Cela dit je ne crois pas qu'une sub soit récursive par elle-même. Cela ne serait même pas dure à vérifier, il faut seulement faire les lignes pour vérifier.
