[PDF] Cours No 4 : Fonctions Récursives.





Previous PDF Next PDF



Cours No 4 : Fonctions Récursives.

i. Un calcul itératif se programme par une boucle (for ou while ou repeat-until). 6. Page 7. Exemple de fonction itérative pour le calcul de factorielle (en C) 



cours 2:Complexité des algorithmes récursifs

?La factorielle de N est définie en fonction de la factorielle de N-1 A l'opposé de la récursion l'itération utilise les structures de contrôle.



Cours 7 – Récursivité I Introduction II Exemples de fonctions

Exemple : Fonction factorielle. Commençons par écrire une version itérative de la fonction factorielle i.e. une fonction.



ALGO 1.1 œ Correction TD N°5.

Calcul de la factorielle d'un entier naturel (avec une structure itérative « Pour »). Variables n : entier factorielle : entier indice : entier.



Récursivité

4/10/2017 1.1 Fonction factorielle. La fonction factorielle fac peut être définie ainsi : ... Écrire une version itérative de la suite de Fibonacci.



Algorithmique et programmation avancée

Une fonction récursive est une fonction qui fait appel à Variante de la fonction factorielle ... Factorielle récursif ? itératif int fact(int n).



Chapitre 18 Algorithmique de base

La méthode itérative nécessite l'utilisation de variables locales pour effectuer le calcul demandé. fonction factorielle(1) a été appelée en rendant 1.



Cours No 4 : Premi`eres Fonctions Récursives 1 Fonctions récursives

Un calcul itératif se programme par une boucle (for ou while ou repeat-until). Exemple de fonction itérative pour le calcul de factorielle (en C).



Correction TP de programmation no3 - Fonctions et procédures

Exercice 1. Fonction factorielle et coefficients du binôme de Newton. La fonction pour calculer la factorielle d'un entier est donnée dans le fichier binome.cpp 



RÉCURSIVITÉ PLAN CALCUL DE FACTORIELLE CODAGE ITÉRATIF

Une fonction récursive n'a pas forcément un argument numérique. def reverse(s): if s == "": return s else: return reverse( 



[PDF] Programmation itérative/récursive - limsi

La fonction factorielle - Cours S2-1 La valeur de la fonction factorielle d'un nombre entier n est le Itératif i = 1 res = 1 while( i



[PDF] Cours No 4 : Fonctions Récursives - LIRMM

Exemple de fonction itérative pour le calcul de factorielle (en C) 1 int fact(n) { // n entier 2 int i = 0; 3 int result = 1; 4 while (i < n){



[PDF] RÉCURSIVITÉ PLAN CALCUL DE FACTORIELLE CODAGE ITÉRATIF

On écrit une fonction récursive appartient testant l'appartenance ou non d'un objet x à une liste L def appartient(L x): if len(L) == 0: return False else:



[PDF] Chapitre 18 Algorithmique de base

Calcul factoriel ? Une approche itérative int factorielle(int i){ int resultat; for(resultat=1;i>1;i--) resultat*=i; return(resultat);



[PDF] cours 2:Complexité des algorithmes récursifs - Esentn

?La factorielle de N est définie en fonction de la factorielle de N-1 A l'opposé de la récursion l'itération utilise les structures de contrôle



[PDF] ALGO 11 œ Correction TD N°5

Calcul de la factorielle d'un entier naturel (avec une structure itérative « Pour ») Variables n : entier factorielle : entier indice : entier



Fonction itérative pour factorielle en PHP - WayToLearnX

15 avr 2020 · Dans ce tutoriel nous allons découvrir comment calculer le factorielle de façon itérative en utilisant la boucle for en PHP Exemple: Fonction 



[PDF] TP Informatique no 3 Récursivité et programmation dynamique

La définition récursive de fonctions est possible en Python Illustrons ce procédé avec la fonction factorielle 1 def factrec(n): 2



Récursif et itératif : factorielle boucle en récursif - France-IOI

Il est cependant possible de donner une définition récursive de la fonction factorielle : La factorielle d'un nombre N vaut 1 si N est égal à 0 et N multiplié 



[PDF] Correction TP de programmation no3

Fonction factorielle et coefficients du binôme de Newton La fonction pour calculer la factorielle d'un entier est donnée dans le fichier binome cpp

  • Comment calculer la complexité d'un algorithme récursif ?

    La complexité d'un algorithme récursif se fait par la résolution d'une équation de récurrence en éliminant la récurrence par substitution de proche en proche.
  • Comment écrire un algorithme récursif ?

    On se propose de reprendre le jeu du Plus-Moins, et d'en écrire un algorithme récursif. Principe : le joueur choisit mentalement un nombre entier entre deux bornes, fixées préala- blement (n et p par exemple), et l'algorithme proc? alors par élimination dichotomique.
  • Comment calculer le factoriel d'un nombre algorithme ?

    Prenons par exemple le calcul de la factorielle d'un nombre, une fonction mathématique qui pour une valeur entière positive, retourne le produit de tous les entiers entre 1 et cette valeur. Pour une valeur nulle, la fonction retourne 1. Par exemple, la factorielle de 5, que l'on note "5", vaut 1*2*3*4*5 = 120.
  • Définition : la programmation récursive est une technique de programmation qui remplace les instructions de boucle (while, for, etc.) par des appels de fonction. et il faut appeler boucle(0). return (s) ; //Pour sommeRec(0, s), le calcul est immédiat } On lance x = sommeRec(0, 100).

Universite Montpellier-II

UFR des Sciences - Departement Informatique - Licence Informatique

Programmation Applicative et Recursive

Cours No 4 : Fonctions Recursives.

Notes de cours

1

6 Induction, recurrence, recursion

{ Une denitioninductived'une partie X d'un ensemble consiste a fournir la donnee explicite de certains elements de X (base) et le moyen de construire de nouveaux elements de X a partir d'elements deja construits. Exemple : l'ensemble des valeurs de la fonction \factorielle" sur les entiers peut ^etre donne parinduction(ou parrecurrence)a partir de la donnee de base \fact(0) = 1" et de la regle \fact(n) =n:fact(n1)". { En informatique, une fonction recursive est une fonction realisant un calcul par recurrence. Exemple : une fonction recursive ecrite en Scheme calculant la valeur de la factorielle d'un nombre. 2

1(define(factn )2(if(=n0)314(?n(fact(-n1)))))3

Une version (partiellement incorrecte) de la fonction recursive factorielle, ecrite en langage C :1intfact (intn )f2if(n== 0)3return1;4else5returnn ?fact(n-1);g4 Apparte : de l'inter^et du type abstrait \GrandNombre" (factorielle calculee avec la fonction C precedente).1factorielle de 5 = 120 2...

3factorielle de 10 = 3628800

4...

5factorielle de 12 = 479001600

6factorielle de 13 = 1932053504

7factorielle de 14 = 1278945280

8factorielle de 15 = 2004310016

9factorielle de 16 = 2004189184

10factorielle de 17 = -2885222405

7 Iteration et recursion

Rappel :Iterer: repeter n fois un processus en faisant changer la valeur des variables jusqu'a obtention du resultat. Calcul iteratif de factorielle d'un nombre :n! =Qni=1i Un calcul iteratif se programme par une boucle (forouwhileourepeat-until). 6 Exemple de fonction iterative pour le calcul de factorielle (en C).

1intfact (n)f//n entier 2inti = 0;3intresult = 1;4while(i aectations et les invariants de boucle. 7

Autre version plus courte en C :

1intfactorielleiterativ e(intn )f2intres = 1;3for(;n>1;n--)res?=n;4returnres ;5gApparte : considerer le sens du calcul entre les versions iteratives et recursives au

vu de l'associativite de la multiplication. 8

8 Exemples de fonction recursives

Multiplication :an=a+a(n1)1(define(multa n )2(if(=n0)304(+a(multa (-n1)))))9 Puissance :an=a:an11(define(expa n )2(if(=n0)314(?a(expa (-n1)))))10

Inverser une cha^ne

Idee :inverse(n) =concatener(dernier(n);inverse(saufDernier(n)))1(define(inverses )2;;string-lengthest une fonction pr efenie3(let((l(string-lengths )))4(if(=l0)5s6(string-append(inverse(substrings 1l)) (substrings 0 1)))))11

9 Autres exemples : Calcul des termes de suites recurrentes

Toute valeur d'une suite recurrente de la forme :

u

0=initialet pourn >1;un= (un1;n)

peut ^etre calculee par une fonction (de n'importe quel langage de programmation autorisant la denition de fonctions recursives) similaire a la fonctionSchemesui- vante :1(define(un )2(if(=n0)3initial4(PHI(u(-n1))n)))Par exemple calcul de factorielle de 5 :

1(defineinitial 1) (definePHI ?)2(u5)-->12012

9.1 Suites arithmetiques

Tout terme d'une suite arithmetique de raisonrde la forme : u

0=initialet pourn >1;un=un1+r

peut ^etre calculee par la fonction1(define(uan r )2(if(=n0)3initial4(+ (ua(-n1)r)r)))Exemple : Multiplication de 4 par 6 :(ua 6 4)avecinitial = 0

13 A noter que le code suivant ne fonctionne pas (voir cours No 3, liaison lexicale) :

1(let((initial0)) (ua3 4))Poureviter de passer par une variable globale ou de passer un parametre

inutile a chaque appel recursif, on peut utiliser une version de la forme speciale

letpermettant de denir des fonctions temporaires et possiblement recursives.1(define(uan r initial )2(letf ((nn ))3(if(=n0)4initial5(+r(f(-n1))))))7(ua6 4 0)8= 2414

9.2 Suites geometriques

Tout terme d'une suite geometrique de raisonqde la forme : u

0=initialet pourn >1;un=q:un1peut ^etre calculee par la fonctionug

suivante :1(define(ugq n initial )2(letf ((nn ))3(if(=n0)4initial5(?q(f(-n1))))))Exemple : 4 puissance 3,

1(ug4 3 1)2= 6415

9.3 Calcul de la somme des termes d'une suite

9.3.1 Exemple historique

La eche de Zenon (philosophe paradoxal) n'arrive jamais a sa cible (ou Achille ne rattrape jamais la tortue) si on decrit le mouvement comme une suite d'etapes : parcourir la moitie de la distance puis la moitie de ce qui reste, puis la moitie de ce qui reste, etc. la eche n'arrive jamais car : lim n!+1P ni=11=2i= 1. Ce que l'on peut verier avec :1(definefzenon (lambda(n)2;;la p artde distanc ep arcouruep arl a eche al 'etapen 3(if(=n1)4(/ 1 (expt2n))5(+ (sz(-n1)) (/ 1 (expt2n))))))16

Plus lisible, utiliser une fonction annexe pour calculer \(/1 (expt 2 n))"1(define(fn ) (/ 1 (expt2n)))3(define(fzenon1n )4(if(=n1)5(f1)6(+ (fn ) (fzenon1(-n1)))))Mais la fonctionfainsi isolee est polluante.

17

La solution suivante est plus elegante.

1(definefzenon2 2(let((f(lambda(n) (/ 1 (expt2n)))))3(letfzenon ((nn ))4(if(=n1)5(f1)6(+ (fn ) (fzenon(-n1)))))))Elle suppose un bonne comprehension de la notion de portee et duree de vie des

identicateurs. 18

9.3.2 Generalisation au calcul de la somme des termes de toute suite

1(define(sommeSuiten )2(if(=n0)3(u0)4(+ (un ) (sommeSuite(-n1)))))A essayer avec :(define (u n) (fact n))

19 Optionnel : m^eme fonctionnalite en n'ecrivant qu'une seule fonction recursive, a condition de passer la fonction du calcul d'un terme en argument. La fonction

somme devient une fonctionnelle ou fonction d'ordre superieur.1(define(sommeSuiten u )2(if(=n1)3(u1)4(+ (sommeSuite(-n1)u) (un ))))On peut par exemple ecrire :

1(somme10 (lambda(n) (/ 1 (exp2n))))20

10 Interpretation d'un appel recursif

Appel recursif: appel realise alors que l'interpretation d'un appel precedent de la m^eme fonction n'est pas acheve. L'interpretation du code d'une fonction recursive passe par une phase d'expansion dans laquelle les appels recursifs sont \empiles" jusqu'a arriver a un appel de la fonction pour lequel une condition d'arr^et est veriee, alors suivie par une phase de contraction dans laquelle les resultats partiels precedemments empiles sont utilises. 21

11 Decouverte d'une solution recursive a des problemes

Disposer d'une solution recursive a un probleme permet d'ecrire simplement un pro- gramme resolvant (calculant quelque chose de relatif a) ce probleme. La decouverte de telles solutions est parfois complexe mais rentable en terme de simplicite d'ex- pression des programmes. 22
Exemple : Algorithme recursif de calcul du pgcd de deux nombres non nuls :

Require:b6= 0

ifb divise athen pgcd(a;b) =b else pgcd(a;b) =pgcd(b;modulo(a;b))) end if

Implantation :1(define(pgcda b )2(if(=b0)3(error" bdoit ˆetrenon n ul")4(let((m(moduloa b )))5(if(=m0)6b7(pgcdb m )))))23

12 Recursivite terminale et non terminale

Appel recursif non terminal: appel recursif argument d'un calcul englobant. Exemple : l'appel recursif dans la denition de factorielle est non terminal car sa valeur est ensuite multipliee par n. Appel recursif terminalappel recursif dont le resultat est celui rendu par la fonction contenant cet appel. Exemple : appel recursif apgcddans la fonction precedente. Propriete : l'interpretation d'un appel recursif terminal peut ^etre realisee sans consommer de pile. Il est possible, en terme de memoire, d'interpreter une fonction recursive terminale comme une fonction iterative car la gestion de la memoire se deduit trivialement des transformations sur les parametres. 24

13 Recursivite croisee

Exemple d'ecole \pair-impair" sur les entiers naturels1(define(pairn )2(or(=n0) (impair(-n1))))4(define(impairn )5(and(not(=n0)) (pair(-n1))))25

Interessant de decouvrir \letrec" pour denir des recursions croisees.

(letrec )Syntax:shouldha vethe form (( ) ...),andshouldb ea sequence of one or more expressions .Itis an errorfor a toapp earmore than once in the list of variablesb eingb ound.Semantics:Thesare b oundto fresh lo cationsholding undefinedv alues,thesare ev aluatedin the r esultingenvironment(ins omeunsp ecifiedorder ),eachisassigned tothe result of the corresp onding,theise valuatedin theresul tingen vironment,andthe v alue(s)ofthe last expression in is(are)returned.Eachbinding of a hasthe en tireletrecexpression as its region ,makingit p ossibleto define m utuallyrecursivepro cedures.26

1(define(pair?n )2(letrec((est-pair?(lambda(n)3(or(=n0) (est-impair?(-n1)))))4(est-impair?(lambda(n)5(and(not(=n0)) (est-pair?(-n1))))))6(est-pair?n )))27

14 Exemples : dessins de gures fractales

Voir,http://classes.yale.edu/fractals/.

Video : \Fractales a la recherche de la dimension cachee", Michel Schwarz et Bill

Jersey, 2010.

Autre cours : \Les images fractales en Scheme, Une exploration des algorithmes recursifs" - Tom Mens - University de Mons-Hainaut (U.M.H.). 28
Programmation avec eets de bord (impressions a l'ecran) :

1;;choisir langage PL T2(require(lib" graphics.ss"" graphics"))3(open-graphics)4(definem ywin(open-viewport" Trianglede Sierpinsky "600 600))5(defineuneCouleur (make-rgb.5 0 .5))29

Exememple des triangles deSierpinski:1(define(s-carr´en x y cote )2;;n nombr ed 'iterations3;;x ,y : c oordoneesdu c oinsup erieurgauche de la gur e4;;c ote: longueur du c arre5(if(= 0n)6((draw-solid-rectanglem ywin) (make-posnx y )cotecote uneCouleur)7(let((moiti´e(/cote2)) (quart(/cote4)))8(s-carr´e(-n1) (+xquart )ymoiti ´e)9(s-carr´e(-n1)x(+ymoiti ´e)moiti´e)10(s-carr´e(-n1) (+xmoiti ´e) (+ymoiti ´e)moiti´e))))30

Figure(1) {(s-carre 8 44 44 600) : sont traces3ninitialcarres de cote \coteinitial=2ninitial", soit pourninitial= 8etcoteinitial= 512,38= 6561 carres, de c^ote512=28= 2. 31
quotesdbs_dbs44.pdfusesText_44

[PDF] fonction itérative php

[PDF] operation factorielle

[PDF] différence entre algorithme itératif et algorithme récursif

[PDF] expression de couturiere

[PDF] fonction récursive

[PDF] automobile in corsa

[PDF] pélican volant de marey (1882)

[PDF] dynamisme d'un cycliste

[PDF] le futurisme mouvement artistique

[PDF] futurisme caractéristiques

[PDF] futurisme définition

[PDF] l5a les clans majeurs pdf

[PDF] l5a pdf

[PDF] l5a 4eme edition pdf

[PDF] pendule élastique vertical