Informatique Cours 1 Explicite, itératif ou récurrent Lycée Jules Ferry Cannes
Informatique Cours 1 Explicite, itératif ou récurrent Lycée Jules Ferry Cannes Page 1 sur 4 TSI2 Figure 1 : Les fractales sont des motifs caractéristiques des suites définies par récurrence. Les suites Lorsque l'on manipule des listes de valeurs (mesures expérimentales) ou que l'on traite des valeurs (valeurs financières par exemple), on est amené à définir des suites de nombres. Dans ce cours on note u, la suite qui à n ∈ associe un nombre u(n)∈. Pour calculer les termes de la suite, on peut définir une fonction dans python qui admet en entrée n et renvoie en sortie la valeur de u(n). 1 Définition explicite de la suite Une suite est définie de façon explicite lorsque les termes u(n) peuvent être calculés par une formule mathématique faisant intervenir n. Exemple simple : 2 En pseudo code (pas normalisé) Fonction puissance_explicte(n) Renvoyer 2**n Fin Fonction puissance_explicite En python def puissance_explicite(n): return 2**n Appel de la fonction dans la console >>> puissance_explicite(3) 8 Informatique Cours 1 Explicite, itératif ou récurrent Lycée Jules Ferry Cannes Page 2 sur 4 TSI2 2 Suite récurrente Une suite n'est pas toujours définie pas une relation explicite à partir de n (soit la relation n'est pas connue, soit ce n'est pas la définition utilisée). Une suite peut être ainsi définie par récurrence à partir des valeurs prises pour les valeurs inférieurs de n à partir de(s) valeur(s) initiale(s). Exemples : récurrence simple : 2. −1 avec 0 1. récurrence double : suite de Fibonacci telle que F(n)=F(n-1)+F(n-2) avec F(0)=0 et F(1)=1 Pour calculer les valeurs de u(n), il existe 2 méthodes de calcul en programmation : - la méthode itérative, - la méthode récurrente. 2.1 Calcul par itération des termes de la suite Il s'agit de calculer successivement toutes les valeurs de u de u(0) jusqu'à u(n). 2.1.1 Algorithme itératif En pseudo code (pas normalisé) Fonction puissance_iteratif(n) s ← 1 Pour i de 1 à n faire s ← s*i Fin Pour Renvoyer s Fin Fonction puissance_iteratif En python : def puissance_iteratif(n): s=1 # condition initiale u(0)=1 for i in range(1,n+1): # calcul itératif des puissances de 2 jusqu'à n s=s*2 return s Utilisation de la fonction >>> puissance_iteratif(3) 8 2.1.2 Compréhension du calcul itératif Pour comprendre le déroulement d'un processus itératif, il est intéressant de dresser une table présentant l'évolution des variables. Exemple avec n=3 Figure 2 : tableau d'évolution des variables dans la boucle. itération initialisation 1e 2e 3e i 1 2 3 s 1 2 4 8 Informatique Cours 1 Explicite, itératif ou récurrent Lycée Jules Ferry Cannes Page 3 sur 4 TSI2 2.2 Calcul par récurrence des termes de la suite Le calcul par récurrence s'obtient par une fonction récursive. Une fonction est récursive lorsqu'elle s'appelle. La fonction récursive est souvent plus courte dans son écriture qu'une fonction itérative mais son fonctionnement est plus difficile à comprendre. Sa vitesse d'exécution n'est pas forcément meilleure. Il faut par contre veiller à bien définir la fin des appels récurrents : - les appels à la fonction se font avec une valeur strictement inférieure à n, - les valeurs initiales mettent fin à la récurrence. Restriction importante: au delà de 1000 étages de récurrence, python affiche une erreur “RuntimeError: maximum recursion depth exceeded” (la pile de calcul est dépassée). 2.2.1 Algorithme récursif En pseudo code (pas normalisé) Fonction puissance_recursif(n) Si n = 1 alors Renvoyer 1 Sinon Renvoyer puissance_recursif(n-1)*2 Fin Si Fin Fonction puissance_recursif En python def puissance_recursif(n): if n==0 : # condition de fin : condition initiale u(0)=1 return 1 else : return puissance_recursif(n-1)*2 # appel récursif Utilisation de la fonction >>> puissance_recursif(3) 8 2.2.2 Compréhension du calcul récursif Le meilleur moyen de comprendre un calcul récursif est de tracer un arbre des appels (l'arbre a plusieurs branches si la récurrence porte sur au moins 2 indices de profondeur) . Exemple pour puissance_recursif(3) Ressources : Damien Broizat Patrick Beynet –UPSTI- u(3)=2.u(2) u(2)=2.u(1) u(1)=2.u(0) u(0)=1 = 2 = 4 = 8 Figure 3 : Arbre des appels par récurrence. Informatique Cours 1 Explicite, itératif ou récurrent Lycée Jules Ferry Cannes Page 4 sur 4 TSI2 Annexe : Pseudo code Affectation a ←1 Opérations arithmétiques Opération Symbole Exemple Résultat addition + 1+2 3 soustraction - 1-2 -1 multiplication * 2*3 6 division / 3/2 1.5 partie entière de la division euclidienne div 5 div 2 2 modulo : reste de la division euclidienne mod 5 mod 2 1 puissance ^ 3^2 9 Opérations de test Comparaison Symbole Exemple Sortie avec a=2 Egale = a = 2 True Pas égale ≠ a ≠ 2 False Supérieur > a > 2 False Supérieur ou égale ≥ a ≥ 2 True Inférieur < a < 2 False Inférieur ou égale ≤ a ≤2 True Instruction conditionnelle Si n mod 2 == 0 alors pair ← vrai Sinon pair ← faux Fin Si Boucle conditionnelle i← 0 k← 0 Tant que i ≠ n faire # n est une donnée i = Entrer ("Donner un nombre entier compris entre 1 et 10 : ") # demande faite à l’utilisateur k← k+1 Fin Tant que Afficher("Gagné en ",k," coups !") Boucle inconditionnelle S← 0 Pour i = 1 à n faire S ← S + i Fin Pour Opérations logiques Symbole négation ~ ou | et & Fonction Fonction negatif(x) s=x Si x > 0 alors s=-s Fin Si Fin Fonction negatif uploads/S4/ 1-cours-fonction-recursive.pdf
Documents similaires
-
19
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Jul 30, 2022
- Catégorie Law / Droit
- Langue French
- Taille du fichier 0.1703MB