Tout 82
Vous souhaitez réagir à ce message ? Créez un compte en quelques clics ou connectez-vous pour continuer.
Rechercher
 
 

Résultats par :
 


Rechercher Recherche avancée

Connexion

Récupérer mon mot de passe

Chatbox externe


Derniers sujets
» [JEU] Mon voisin du dessous
Récursivité en TI-Basic EmptyDim 16 Oct 2022 - 21:11 par Wistaro

» Bonne année 2018!
Récursivité en TI-Basic EmptyVen 2 Nov 2018 - 19:42 par Ti64CLi++

» Lancement du TI-Concours 2017 !
Récursivité en TI-Basic EmptySam 20 Mai 2017 - 0:27 par Paulo1026

» Chaînes Youtube des membres
Récursivité en TI-Basic EmptyVen 19 Mai 2017 - 22:41 par Wistaro

» cacul du taux d'intêret
Récursivité en TI-Basic EmptyVen 24 Mar 2017 - 21:50 par m@thieu41

» [Projet] Un mario by tout82
Récursivité en TI-Basic EmptyDim 29 Jan 2017 - 14:09 par Wistaro

» Cherche documentation assembleur TI82stat
Récursivité en TI-Basic EmptyMer 25 Jan 2017 - 12:29 par Ti64CLi++

» Probleme Ti-82 Stats fr
Récursivité en TI-Basic EmptyJeu 12 Jan 2017 - 13:56 par Ti64CLi++

» ROM 82 stats.fr
Récursivité en TI-Basic EmptyJeu 15 Déc 2016 - 10:24 par Ti64CLi++

Partenaires
TI-Planet Espace-TI : Forum

Faire un don à Tout-82...
Où va cet argent ?
Membres donateurs:- Persalteas (10€)
- Wistaro (5€)
- jo2geek (22€)

Les posteurs les plus actifs du mois
Aucun utilisateur

-17%
Le deal à ne pas rater :
Casque de réalité virtuelle Meta Quest 2 128 Go Blanc (+29,99€ ...
249.99 € 299.99 €
Voir le deal

Récursivité en TI-Basic

5 participants

Aller en bas

Récursivité en TI-Basic Empty Récursivité en TI-Basic

Message par Linkakro Mar 11 Fév 2014 - 22:35

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.
Linkakro
Linkakro
----------------------
----------------------

Messages : 533
Points Concours : 55
Productivité : 31
Date d'inscription : 30/07/2013
Localisation : origine région centre, puis perpignan
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Revenir en haut Aller en bas

Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic

Message par jo2geek Mar 11 Fév 2014 - 23:17

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
Récursivité en TI-Basic Screen14


Dernière édition par jo2geek le Mer 12 Fév 2014 - 7:28, édité 1 fois

jo2geek
Connaisseur
Connaisseur

Messages : 116
Points Concours : 81
Productivité : 9
Date d'inscription : 27/01/2014
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Revenir en haut Aller en bas

Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic

Message par Linkakro Mer 12 Fév 2014 - 0:17

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.
Linkakro
Linkakro
----------------------
----------------------

Messages : 533
Points Concours : 55
Productivité : 31
Date d'inscription : 30/07/2013
Localisation : origine région centre, puis perpignan
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Revenir en haut Aller en bas

Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic

Message par persalteas Mer 12 Fév 2014 - 16:10

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

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

Messages : 483
Points Concours : 152
Productivité : 39
Date d'inscription : 06/12/2012
Localisation : Savoie, France
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

https://tout82.forumactif.org

Revenir en haut Aller en bas

Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic

Message par Wistaro Mer 12 Fév 2014 - 22:26

Très beau tutoriel, +1! Smile

(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...)
Wistaro
Wistaro
Passioné
Passioné

Messages : 918
Points Concours : 86
Productivité : 28
Date d'inscription : 16/06/2013
Localisation : Tarbes - DUT GEII
Calculatrice(s) :
  • TI-82
  • TI-82 Stats
  • TI-82 Stats.fr

. : TI-82 Stats.fr

https://www.youtube.com/user/Wistaro

Revenir en haut Aller en bas

Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic

Message par Linkakro Jeu 13 Fév 2014 - 0:13

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.
Linkakro
Linkakro
----------------------
----------------------

Messages : 533
Points Concours : 55
Productivité : 31
Date d'inscription : 30/07/2013
Localisation : origine région centre, puis perpignan
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Revenir en haut Aller en bas

Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic

Message par noelthebest Jeu 13 Fév 2014 - 13:40

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

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

Enfin, bien joué. 🆗

noelthebest
Intéressé
Intéressé

Messages : 83
Points Concours : 0
Productivité : 0
Date d'inscription : 02/06/2013

Revenir en haut Aller en bas

Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum