Récursivité en TI-Basic

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 :

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

Ici la définition de la solution pour un certain nombre de plateaux utilise la même définition pour d'autres nombres de plateaux.
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
    }
  }
}

En récursivité, on peut choisir le nombre de boucles à l'exécution et ne coder qu'une seule boucle.

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.

bravo pour ce cours ! +1
itération ou récursivité il faut bien choisir selon le besoin
la récursivité est efficace mais un peu plus dure à appréhender (à mon avis)
par paresse je préfère souvent quand je peux l'itération...

69! je préfère faire

Certes c'est l'approche la plus évidente de ce problème. Je ne l'ai pas détaillé ni en TI-Basic ni en C. Je prend note pour une éventuelle mise à jour.

C'est un bon article, surtout que tu avais éveillé ma curiosité sur le sujet

Ensuite, je ne suis pas sur que ce soit à la portée du premier venu... C'est technique, quand même Mais pratique, certes.

Très beau tutoriel, +1!

(Même si, je l' avoue, j'ai pas tout compris certains points....En effet, je doute que la récursivité soit au programme de 1ère S, de même que la factorielle...)

La factorielle tu verras ça en dénombrement et donc probabilités.
(n!)=n*...*2*1 et (0!)=1

Je suis ouvert aux suggestions, je ne prétend pas écrire quelque chose de suffisant du premier coup. Surtout qu'il manque souvent des choses basiques dans mes écrits.

J'avais essayé ça il n'y a pas si longtemps. Mais je n'y étais pas arrivé.

Ce qui est amusant, c'est que j'avais moi aussi testé sur la factorielle...

Enfin, bien joué.