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
Mar 10 Oct 2017 - 19:42 par Wistaro

» Lancement du TI-Concours 2017 !
Sam 20 Mai 2017 - 0:27 par Paulo1026

» Chaînes Youtube des membres
Ven 19 Mai 2017 - 22:41 par Wistaro

» cacul du taux d'intêret
Ven 24 Mar 2017 - 21:50 par m@thieu41

» [Projet] Un mario by tout82
Dim 29 Jan 2017 - 14:09 par Wistaro

» Cherche documentation assembleur TI82stat
Mer 25 Jan 2017 - 12:29 par Ti64CLi++

» Probleme Ti-82 Stats fr
Jeu 12 Jan 2017 - 13:56 par Ti64CLi++

» ROM 82 stats.fr
Jeu 15 Déc 2016 - 10:24 par Ti64CLi++

» flappy bird
Jeu 15 Déc 2016 - 10:23 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


Récursivité en TI-Basic

Voir le sujet précédent Voir le sujet suivant Aller en bas

Récursivité en TI-Basic

Message par Linkakro le 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.

__________________________________________________________________________
Vétéran du TI-Basic Zilog80. Ti82statfr sur Tout82 depuis 2009 et ti84pocketfr depuis noël 2012. Ti83plusfrUSB (été 2014, concours tiplanet suite du geek). Bidouille un peu d'assembleur Z80.
Incappable de gérer le temps et manque de tact, plutôt serviable.
Je prend les commandes de programme. Je suis motivé par les maths et la physique tant que ce n'est pas une simple copie d'antisèche.
Vous pouvez trouver une grande partie de mes données hébergées dans mon mediafire. Le ZIP et la liste sont périmées depuis longtemps.
coucou Invité What a Face
avatar
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

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Récursivité en TI-Basic

Message par jo2geek le 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


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

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Récursivité en TI-Basic

Message par Linkakro le 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.

__________________________________________________________________________
Vétéran du TI-Basic Zilog80. Ti82statfr sur Tout82 depuis 2009 et ti84pocketfr depuis noël 2012. Ti83plusfrUSB (été 2014, concours tiplanet suite du geek). Bidouille un peu d'assembleur Z80.
Incappable de gérer le temps et manque de tact, plutôt serviable.
Je prend les commandes de programme. Je suis motivé par les maths et la physique tant que ce n'est pas une simple copie d'antisèche.
Vous pouvez trouver une grande partie de mes données hébergées dans mon mediafire. Le ZIP et la liste sont périmées depuis longtemps.
coucou Invité What a Face
avatar
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

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Récursivité en TI-Basic

Message par persalteas le 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.

__________________________________________________________________________
Bienvenue sur le nouveau Tout-82, Invité ! Viens discuter sur le chat... What a Face
Depuis que je me suis tatoué une calculatrice sur le bras, vous pouvez compter sur moi ! :P (Best joke ever x) )
avatar
persalteas
----------------------
----------------------

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

. : TI-82 Stats.fr

Voir le profil de l'utilisateur http://tout82.forumactif.org

Revenir en haut Aller en bas

Re: Récursivité en TI-Basic

Message par Wistaro le 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...)

__________________________________________________________________________
Clique ici pour retrouver tout mes programmes en TIbasic

Tu es curieux, Invité? Alors clique ici:


Coucou Invité !Ta dernière visite sur ce forum date de Jeu 1 Jan 1970 . Tu as posté un total de 78 message(s) sur Tout 82 et enfin, tu as 0 ans.
Si nous sommes le 0, je te souhaite un joyeux anniversaire ;-)

avatar
Wistaro
Passioné
Passioné

Messages : 910
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

Voir le profil de l'utilisateur http://www.youtube.com/user/Wistaro

Revenir en haut Aller en bas

Re: Récursivité en TI-Basic

Message par Linkakro le 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.

__________________________________________________________________________
Vétéran du TI-Basic Zilog80. Ti82statfr sur Tout82 depuis 2009 et ti84pocketfr depuis noël 2012. Ti83plusfrUSB (été 2014, concours tiplanet suite du geek). Bidouille un peu d'assembleur Z80.
Incappable de gérer le temps et manque de tact, plutôt serviable.
Je prend les commandes de programme. Je suis motivé par les maths et la physique tant que ce n'est pas une simple copie d'antisèche.
Vous pouvez trouver une grande partie de mes données hébergées dans mon mediafire. Le ZIP et la liste sont périmées depuis longtemps.
coucou Invité What a Face
avatar
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

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Récursivité en TI-Basic

Message par noelthebest le 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

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Récursivité en TI-Basic

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut


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