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

View - Download Cours No 4 : Fonctions Récursives.

Previous PDF

Next PDF

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] 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

[PDF] l5a 4eme edition pdf download

[PDF] pendule elastique definition