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

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

Previous PDF

Next PDF

Universit´e Montpellier-II

UFR des Sciences - D´epartement Informatique - Licence Informatique UE GLIN302 - Programmation Applicative et R´ecursive

Cours No 4 : Premi`eres Fonctions R´ecursives

Notes de cours - 2007-20121 Fonctions r´ecursives

1.1 Principe

Une d´efinition inductive d"une partie X d"un ensemble consiste `a fournir la donn´ee explicite de certains ´el´ements

de X (base) et le moyen de construire de nouveaux ´el´ements de X `a partir d"´el´ements d´ej`a construits.

Exemple : ensemble des valeurs de la fonction "factorielle" sur les entiers peut ˆetre donn´e par la fonction

r´ecursive suivante `a partir de la donn´ee de base "fact(0) = 1" et de la r`egle "fact(n) =n.fact(n-1)".1(define(factn)

2(if(=n0)

314(?n(fact(-n1)))))

Fonction r´ecursive : fonction dont la d´efinition inclus (au moins) un appel `a elle-mˆeme.

Une autre version, en C :1intfact(intn){2if(n== 0)

3return1;

4else

5returnn?fact(n-1);}R´eflexion : consid´erer le sens du calcul entre les versions it´eratives et r´ecursives au vu de l"associativit´e de la

multiplication.

Appart´e : de l"int´erˆet du type abstrait "GrandNombre" (factorielle calcul´ee avec la fonction pr´ec´edente).1factorielle de 0 = 1

2factorielle de 1 = 1

3factorielle de 2 = 2

4factorielle de 3 = 6

5factorielle de 4 = 24

6factorielle de 5 = 120

7factorielle de 6 = 720

8factorielle de 7 = 5040

9factorielle de 8 = 40320

10factorielle de 9 = 362880

11factorielle de 10 = 3628800

12factorielle de 11 = 39916800

13factorielle de 12 = 4790016001

14factorielle de 13 = 1932053504

15factorielle de 14 = 1278945280

16factorielle de 15 = 2004310016

17factorielle de 16 = 2004189184

18factorielle de 17 = -2885222401.2 It´eration et r´ecursion

Rappel :It´erer: r´ep´eter n fois un processus en faisant changer la valeur des variables jusqu"a obtention du

r´esultat. Calcul it´eratif de factorielle d"un nombre :n! =?ni=1i Un calcul it´eratif se programme par une boucle (forouwhileourepeat-until). Exemple de fonction it´erative pour le calcul de factorielle (en C).1intfact(n){//nentier

2inti= 0;

3intresult= 1;

6i=i+ 1;

7result=result?i;

8//result=fact(i)--invariantdeboucle

9}10//i=n

11return(result);}Inconv´enient : n´ecessit´e de g´erer explicitement l"´evolution des variables, l"ordre des affectations et les invariants

de boucle. Autre version plus courte en C :1intfactorielleiterative(intn){2intres= 1;

3for(;n>1;n--)res?=n;

4returnres;

5}1.3 Autres Exemples de fonction r´ecursives simples

Multiplication :an=a+a(n-1)1(define(multan)

2(if(=n0)

304(+a(multa(-n1)))))

Puissance :an=a.an-11(define(expan)

2

2(if(=n0)

314(?a(expa(-n1)))))

Inverser une chaˆıne

Id´ee :inverse(n) =concatener(dernier(n),inverse(saufDernier(n)))1(define(inverses)

3(let((l(string-lengths)))

4(if(=l0)

5s

6(string-append(inverse(substrings1l)) (substrings0 1)))))

1.4 Exemple : Calcul des termes de suites r´ecurrentes

Toute valeur d"une suite r´ecurrente de la forme : u

0=initialet pourn >1,un= Φ(un-1,n)

peut ˆetre calcul´ee par une fonction (de n"importe quel langage de programmation autorisant la d´efinition de

fonctions r´ecursives) similaire `a la fonctionSchemesuivante :1(define(un)

2(if(=n0)

3initial

4(PHI(u(-n1))n)))

Par exemple calcul de factorielle de 5 :

1(defineinitial1) (definePHI?)2(u5)-->1201.4.1 Suites arithm´etiques

Tout terme d"une suite arithm´etique de raisonrde la forme : u

0=initialet pourn >1,un=un-1+r

peut ˆetre calcul´ee par la fonction1(define(uanr)

2(if(=n0)

3initial

4(+ (ua(-n1)r)r)))

Exemple : Multiplication de 4 par 6 : (ua 6 4) avec initial = 0

A noter que le code suivant ne fonctionne pas (voir cours No 3, liaison lexicale) :1(let((initial0)) (ua3 4))

3

Pour´eviter de passer par une variable globale ou de passer un param`etre `a chaque appel r´ecursif,

on peut utiliser une version de la forme sp´ecialeletpermettant de d´efinir des fonctions internes, temporaires

et r´ecursives.1(define(uanrinitial)

2(letf((nn))

3(if(=n0)

4initial

5(+r(f(-n1))))))

6

7(ua6 4 0)

8= 241.4.2 Suites g´eom´etriques

Tout terme d"une suite g´eom´etrique de raisonqde la forme : u

0=initialet pourn >1,un=q.un-1peut ˆetre calcul´ee par la fonction ug suivante :1(define(ugqninitial)

2(letf((nn))

3(if(=n0)

4initial

5(?q(f(-n1))))))

Exemple : 4 puissance 3,

1(ug4 3 1)

2= 641.5 Calcul de la somme des termes d"une suite

1.5.1 Exemple historique

La fl`eche de Z´enon (philosophe paradoxal) n"arrive jamais `a sa cible (ou Achille ne rattrape jamais la tortue) si

on d´ecrit le mouvement comme une suite d"´etapes : parcourir la moiti´e de la distance puis la moiti´e de ce qui

reste, puis la moiti´e de ce qui reste, etc. la fl`eche n"arrive jamais car : lim n→+∞? ni=11/2i= 1. Ce que l"on peut v´erifier avec :1(definefzenon(lambda(n)

3(if(=n1)

4(/ 1 (expt2n))

5(+ (sz(-n1)) (/ 1 (expt2n))))))

Plus lisible, utiliser une fonction annexe pour calculer "(/1 (expt 2 n))"

1(define(fn) (/ 1 (expt2n)))

2 4

3(define(fzenon1n)

4(if(=n1)

5(f1)

6(+ (fn) (fzenon1(-n1)))))

Mais la fonction f ainsi isol´ee est polluante. La solution suivante est plus ´el´egante.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 compr´ehension de la notion de port´ee et dur´ee de vie des identificateurs.

1.5.2 G´en´eralisation au calcul de la somme des termes de toute suite1(define(sommeSuiten)

2(if(=n0)

3(u0)

4(+ (un) (sommeSuite(-n1)))))

A essayer avec : (define (u n) (fact n))

Optionnel : mˆeme fonctionnalit´e en n"´ecrivant qu"une seule fonction r´ecursive, `a condition de passer la fonction

du calcul d"un terme en argument. La fonction somme devient une fonctionnelle ou fonction d"ordre sup´erieur.1(define(sommeSuitenu)

2(if(=n1)

3(u1)

4(+ (sommeSuite(-n1)u) (un))))

On peut par exemple ´ecrire :

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

1.6 Interpr´etation d"un appel r´ecursif

Appel r´ecursif: appel r´ealis´e alors que l"interpr´etation d"un appel pr´ec´edent de la mˆeme fonction n"est pas

achev´e.

L"interpr´etation du code d"une fonction r´ecursive passe par une phase d"expansion dans laquelle les appels

r´ecursifs sont "empil´es" jusqu"`a arriver `a un appel de la fonction pour lequel une condition d"arrˆet est v´erifi´ee,

alors suivie par une phase de contraction dans laquelle les r´esultats partiels pr´ec´edemments empil´es sont utilis´es.5

1.7 D´ecouverte d"une solution r´ecursive `a des probl`emes

Disposer d"une solution r´ecursive `a un probl`eme permet d"´ecrire simplement un programme r´esolvant (calculant

quelque chose de relatif `a) ce probl`eme. La d´ecouverte de telles solutions est parfois complexe mais rentable en

terme de simplicit´e d"expression des programmes.

Exemple : Algorithme r´ecursif de calcul du pgcd de deux nombres non nuls :Require:b?= 0ifb divise athenpgcd(a,b) =belse

pgcd(a,b) =pgcd(b,modulo(a,b)))end if

Implantation en Scheme :1(define(pgcdab)

2(if(=b0)

3(error"bdoitˆetrenonnul")

4(let((m(moduloab)))

5(if(=m0)

6b

7(pgcdbm)))))

1.8 R´ecursivit´e terminale et non terminale

Appel r´ecursif non terminal: appel r´ecursif argument d"un calcul englobant.

Exemple : l"appel r´ecursif dans la d´efinition de factorielle est non terminal car sa valeur est ensuite multipli´ee

par n.

Appel r´ecursif terminalappel r´ecursif dont le r´esultat est celui rendu par la fonction contenant cet appel.

Exemple : appel r´ecursif `a pgcd dans la fonction pr´ec´edente.

Propri´et´e : l"interpr´etation d"un appel r´ecursif terminal peut ˆetre r´ealis´ee sans consommer de pile.

Il est possible, en terme de m´emoire, d"interpr´eter une fonction r´ecursive terminale comme une fonction it´erative

car la gestion de la m´emoire se d´eduit trivialement des transformations sur les param`etres.

1.9 R´ecursivit´e crois´ee

Exemple d"´ecole "pair-impair" sur les entiers naturels1(define(pairn)

2(or(=n0) (impair(-n1))))

3

4(define(impairn)

5(and(not(=n0)) (pair(-n1))))

Int´eressant de d´ecouvrir "letrec" pour d´efinir des r´ecursions crois´ees. (letrec )Syntax:shouldhavetheform(( ) ...),6 variablesbeingbound. recursiveprocedures.

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

1.10 Fonctions de dessin de figures fractales

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

Vid´eo : "Fractales `a la recherche de la dimension cach´ee", Michel Schwarz et Bill Jersey, 2010.

Autre cours : "Les images fractales en Scheme, Une exploration des algorithmes r´ecursifs" - Tom Mens -

University de Mons-Hainaut (U.M.H.).

Programmation avec effets de bord (impressions `a l"´ecran) :1;;choisirlangagePLT

2(require(lib"graphics.ss""graphics"))

3(open-graphics)

4(definemywin(open-viewport"TriangledeSierpinsky"600 600))

5(defineuneCouleur(make-rgb.5 0 .5))

Exememple des triangles deSierpinski:1(define(s-carr´enxycote)

2;;nnombred"it´erations

4;;cote:longueurducarr´e

5(if(= 0n)

6((draw-solid-rectanglemywin) (make-posnxy)cotecoteuneCouleur)

7(let((moiti´e(/cote2)) (quart(/cote4)))

8(s-carr´e(-n1) (+xquart)ymoiti´e)

10(s-carr´e(-n1) (+xmoiti´e) (+ymoiti´e)moiti´e))))

7

Fig.1 - (s-carr´e 8 44 44 600) : sont trac´es 3ninitialcarr´es de cot´e "coteinitial/2ninitial", soit pourninitial= 8 et

cote initial= 512, 38= 6561 carr´es, de cˆot´e 512/28= 2.8quotesdbs_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