Un petit tutoriel improvisé ce soir sur la récursivité. Je me base sur ma propre expérience, en particulier pour la TI.
Récurrence et récursivité
La récurrence est l'utilisation répétée d'un procédé, avec utilisation d'un résultat comme donnée pour l'usage suivant.
factorielle n! : u(n+1)=n*u(n) et u(0)=1
donc u(1)=1
u(2)=2
u(3)=6
u(4)=24
La récursivité est la définition d'un procédé à partir de lui même. Les données initiales ne sont pas toujours connues au commencement.
factorielle n! : u(n)=n*u(n-1) et u(0)=1
u(4)=4*u(3)
=4*3*u(2)
=4*3*2*1*u(0)
=4*3*2*1*1
=4*3*2*1
=4*3*2
=4*6
=24
Mes exemples laissent le choix entre les méthodes, mais il existent d'autres problèmes dans lesquels une seule méthode convient.
J'illustre d'un point de vue fonctionnel en langage C :
Un exemple de problème adapté à la récursivité
Je prend un exemple en syntaxe C : les tours de hanoi.
C'est récursif.
On voit bien que des choses sont déterminées au fur et à mesure, alors que le nombre de plateau évolue au contraire vers une donnée connue. La récursivité est pratique pour ça.
Economies
La meilleur utilisation que j'ai trouvé est l'économie de code et permettre un nombre indéfini d'itérations.
Exemple avec un crible.
En récurrence simple on écrit des boucles les unes dans les autres, et on doit les prévoir à l'avance.
Et pour choisir le nombre de boucles à utiliser au moment de l'exécution, il faudrait en plus une cascade d'alternatives.
exemple
Ma première méthode dans une TI
La TI n'a pas de variable locale donc toutes les données doivent être gérées de manière globales, quel que soit l'usage.
J'ai retenu de stocker les données dans une liste, une chaine ou une matrice, et de se repérer dedans en utilisant un pointeur qui sera manuellement incrémenté et décrémenté au besoin.
Exemple de factorielle
Exemple de crible, c'est le plus parlant à mon sens.
C'est d'ailleurs la première chose que j'aie programmé en récursif, sur une TI qui-plus-est. Il s'agissait d'un calculateur de décomposition de produit en facteurs quelconques.
factorisation récursive FACT+FACTZ
En revanche mon exemple des tours de hanoï ne serait pas pertinent, car j'ai trouvé comment faire autrement, sans liste de stockage.
Au moins une exception à cette méthode de liste
Il existe des problèmes pour lesquels les données n'ont pas besoin d'être sauvegardées car quelques calculs suffisent pour retrouver l'état précédent.
C'est le cas de mon programme des tours de hanoi. Il suffit de calculer l'intermédiaire à partir des deux autres et réciproquement. Une variable numérique supplémentaire suffit pour l'appel de la fonction pour n=1, même pas besoin de liste pour revenir à l'état précédent.
Autre méthode de simulation de récursivité dans une TI
Ce que je conçois souvent en récursivité peut être géré avec une boucle, une liste et un pointeur, au prix de quelques tests.
http://tout82.free.fr/forum/sujet.php?sujet=3890
Je n'ai pas trouvé d'idée de comment amener cette méthode de manière un peu plus générale que dans le programme où elle m'a été présentée. Une telle présentation est toujours possible plus tard.
Conclusion
La récursivité est une manière inhabituelle de construire des raisonnements et des programmes, et qui peut s'avérer efficace tout en permettant des économies, mais qui peut nécessiter des travaux supplémentaires en langage TI-Basic.
Récurrence et récursivité
La récurrence est l'utilisation répétée d'un procédé, avec utilisation d'un résultat comme donnée pour l'usage suivant.
factorielle n! : u(n+1)=n*u(n) et u(0)=1
donc u(1)=1
u(2)=2
u(3)=6
u(4)=24
La récursivité est la définition d'un procédé à partir de lui même. Les données initiales ne sont pas toujours connues au commencement.
factorielle n! : u(n)=n*u(n-1) et u(0)=1
u(4)=4*u(3)
=4*3*u(2)
=4*3*2*1*u(0)
=4*3*2*1*1
=4*3*2*1
=4*3*2
=4*6
=24
Mes exemples laissent le choix entre les méthodes, mais il existent d'autres problèmes dans lesquels une seule méthode convient.
J'illustre d'un point de vue fonctionnel en langage C :
- Code:
void main(void)
{
factorielle(4);
}
int factorielle(int n)
{
if(n==0)
{
return 1
}
else
{
return n*factorielle(n-1);
}
}
Un exemple de problème adapté à la récursivité
Je prend un exemple en syntaxe C : les tours de hanoi.
- Code:
void main(void)
{
hanoi(3,1,2,3); // trois plateaux, à déplacer de la tour 1 vers 2, en utilisant l'intermédiaire 3.
}
void hanoi(combien,depart,arrivee,intermed) // je veux déplacer de depart vers arrivee en utilisant intermed
{
if(combien==1)
{
printf("deplace %d vers %d",depart,arrivee); // déplace un seul plateau directement
}
else
{ // pour déplacer combien plateaux de depart vers arrivee, j'ai besoin...
hanoi(combien-1,depart,intermed,arrivee); // ...deplacer le dessus de la pile vers l'intermed...
hanoi(1,depart,arrivee,intermed); // ...déplacer le plateau qui reste en bas vers la destination...
hanoi(combien-1,intermed,arrivee,depart); // ... déplacer le dessus de pile, qui est sur intermed, vers l'arrivee
}
}
C'est récursif.
On voit bien que des choses sont déterminées au fur et à mesure, alors que le nombre de plateau évolue au contraire vers une donnée connue. La récursivité est pratique pour ça.
Economies
La meilleur utilisation que j'ai trouvé est l'économie de code et permettre un nombre indéfini d'itérations.
Exemple avec un crible.
En récurrence simple on écrit des boucles les unes dans les autres, et on doit les prévoir à l'avance.
Et pour choisir le nombre de boucles à utiliser au moment de l'exécution, il faudrait en plus une cascade d'alternatives.
exemple
- Code:
for(a=0;a<=9;a++)
{
for(b=0;b<=9;b++)
{
for(c=0;c<=9;c++)
{
... // d'autres imbrications, c'est possible mais pénible
}
}
}
- Code:
void main(void)
{
recursion(3); // n=3 boucles encapsulées
}
void recursion(int n)
{
for(a=0;a<=9;a++)
{
if(n>0)
{
recursion(n-1);
}
}
}
Ma première méthode dans une TI
La TI n'a pas de variable locale donc toutes les données doivent être gérées de manière globales, quel que soit l'usage.
J'ai retenu de stocker les données dans une liste, une chaine ou une matrice, et de se repérer dedans en utilisant un pointeur qui sera manuellement incrémenté et décrémenté au besoin.
Exemple de factorielle
- Code:
Prompt N
1->F
prgmFACTRL
- Code:
//prgm Factrl
N-1->N
If N>0
prgmFACTRL
N+1->N
F*N->F
Return // facultatif car à la fin
Exemple de crible, c'est le plus parlant à mon sens.
- Code:
Prompt N
1->J
ClrList L1
prgmRECUR
- Code:
// prgm RECUR
For(A,1,9
If J<N
Then
A->L1(J
J+1->J
prgmRECUR
J-1->J
L1(J->A
End
End
Return // facultatif car à la fin
C'est d'ailleurs la première chose que j'aie programmé en récursif, sur une TI qui-plus-est. Il s'agissait d'un calculateur de décomposition de produit en facteurs quelconques.
factorisation récursive FACT+FACTZ
En revanche mon exemple des tours de hanoï ne serait pas pertinent, car j'ai trouvé comment faire autrement, sans liste de stockage.
Au moins une exception à cette méthode de liste
Il existe des problèmes pour lesquels les données n'ont pas besoin d'être sauvegardées car quelques calculs suffisent pour retrouver l'état précédent.
C'est le cas de mon programme des tours de hanoi. Il suffit de calculer l'intermédiaire à partir des deux autres et réciproquement. Une variable numérique supplémentaire suffit pour l'appel de la fonction pour n=1, même pas besoin de liste pour revenir à l'état précédent.
Autre méthode de simulation de récursivité dans une TI
Ce que je conçois souvent en récursivité peut être géré avec une boucle, une liste et un pointeur, au prix de quelques tests.
http://tout82.free.fr/forum/sujet.php?sujet=3890
Je n'ai pas trouvé d'idée de comment amener cette méthode de manière un peu plus générale que dans le programme où elle m'a été présentée. Une telle présentation est toujours possible plus tard.
Conclusion
La récursivité est une manière inhabituelle de construire des raisonnements et des programmes, et qui peut s'avérer efficace tout en permettant des économies, mais qui peut nécessiter des travaux supplémentaires en langage TI-Basic.