Récursivité en TI-Basic Hitskin_logo Hitskin.com

Ceci est une prévisualisation d'un thème de Hitskin.com
Installer le thèmeRetourner sur la fiche du thème

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

Jeu 28 Mar 2024 - Bienvenue,

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

Le Deal du moment :
Xiaomi Mi Smart Camera 2K Standard Edition (design ...
Voir le deal
11.39 €

Vous n'êtes pas connecté. Connectez-vous ou enregistrez-vous

Récursivité en TI-Basic

5 participants

Aller en bas  Message [Page 1 sur 1]

1Récursivité en TI-Basic Empty Récursivité en TI-Basic Mar 11 Fév 2014 - 22:35

Linkakro

Linkakro
----------------------
----------------------

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.

2Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic Mar 11 Fév 2014 - 23:17

jo2geek


Connaisseur
Connaisseur

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

3Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic Mer 12 Fév 2014 - 0:17

Linkakro

Linkakro
----------------------
----------------------

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.

4Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic Mer 12 Fév 2014 - 16:10

persalteas

persalteas
----------------------
----------------------

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.

https://tout82.forumactif.org

5Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic Mer 12 Fév 2014 - 22:26

Wistaro

Wistaro
Passioné
Passioné

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

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

6Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic Jeu 13 Fév 2014 - 0:13

Linkakro

Linkakro
----------------------
----------------------

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.

7Récursivité en TI-Basic Empty Re: Récursivité en TI-Basic Jeu 13 Fév 2014 - 13:40

noelthebest


Intéressé
Intéressé

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é. 🆗

Contenu sponsorisé



Revenir en haut  Message [Page 1 sur 1]

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