[PDF] Chapitre 1 : introduction aux fonctions récursives Table des mati

View - Download Chapitre 1 : introduction aux fonctions récursives Table des mati

Previous PDF

Next PDF

Chapitre 1 : introduction aux fonctions recursives

Table des matieres

1 Revisions et complements sur les fonctions 1

1.1 Les notions et le vocabulaire a ma^triser . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Les variables locales a une fonction : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Une fonction peut appeler une autre fonction et m^eme renvoyer une autre fonction! 2

2 Nouveaute : une fonction peut s'appeler elle-m^eme 3

2.1 Denition et parallelisme avec la recurrence . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Comment ca marche une fonction recursive? . . . . . . . . . . . . . . . . . . . . . . . . 3

2.3 Points importants a retenir pour une fonction recursive . . . . . . . . . . . . . . . . . . 4

3 Versions recursives d'algorithmes vus en premiere annee 5

3.1 L'algorithme d'Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3.2 Algorithme de Horner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.2.1 Methode

≪naturelle≫d'evaluation d'un polyn^ome . . . . . . . . . . . . . . . . 6

3.2.2 L'idee de la methode de Horner (1ere annee) . . . . . . . . . . . . . . . . . . . . 6

3.2.3 Ecriture recursive de Horner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.3 Exponentiation rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.3.1 L'algorithme

≪naif≫pour le calcul des puissances . . . . . . . . . . . . . . . . 7

3.3.2 Rappels sur l'idee de l'exponentiation rapide et implementation recursive . . 7

3.4 Une morale provisoire : le recursif c'est plus facile? . . . . . . . . . . . . . . . . . . . . 8

4 Encore plus de recursion : recursion multiple 8

4.1 Eviter de multiplier les appels recursifs inutiles . . . . . . . . . . . . . . . . . . . . . . . 8

4.2 Des fonctions qui sontvraimentdoublement recursives . . . . . . . . . . . . . . . . . . 9

4.3 Des suites recurrentes croisees l'une avec l'autre : recursivite croisee . . . . . . . . . . 9

5 Les trois questions qu'on doit se poser sur un algorithme : le cas des fonctions

recursives10

5.1 Rappel de premiere annee : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

5.2 Le cas des fonctions recursives sur l'exemple de l'exp. rapide . . . . . . . . . . . . . . . 10

1 Revisions et complements sur les fonctions

1.1 Les notions et le vocabulaire a ma^triserDenition :Une fonction informatiquefest un objet qui prend desarguments(ou dit

aussi parametres) et quirenvoiedesvaleurs de retours(ou pasa.). Une fonction peut modier son ou ses arguments si les arguments en question sont des objetsmodiablesb(des listes par exemple).a. Dans ce cas, elle renvoie unNone

b. on dit aussimutables?Denition d'une fonction avec le mot-clefdef:enPython, on sait que la syntaxe de

denitiond'une fonction est, par exemple pour la fonction mathematiquef?x↦x2: def f(x) : # x est ici l'unique argument de f return x*x Le fait decalculerf(2)s'appelle unappelde la fonctionf. Dans le langage informatique, on dit aussi qu'onpasse2 comme argument a la fonctionf.

En python, il sut de taperf(2).

1 ?Denition d'une fonction avec le mot-cleflambda: la m^eme fonction peut ^etre declaree en une ligne comme suit : f=lambda x : x*x Pour les optionnaires d'info. comparer a la syntaxe Caml ... 1 On peut encore appelerf(2). Mais on va voir ci-apres qu'un inter^et de la declaration avec lambdaest eventuellement de ne pas donner de nom a la fonction. ?Un exemple de fonction qui ne retourne rien, mais modie son argument : def ajoute0(L): """prend une liste en argument et la modifie en rajoutant 0"""

L.append(0)

Question :Donner les valeurs deLetMsi on fait :

L=[1,2]

M=ajoute0(L)

1.2 Les variables locales a une fonction :

Regle : chaque variable aectee a l'interieur d'une fonction est une variablelocale.

Exemple simple :que fait le code ci-dessous?

a=2 def renvoieun(): a=1 return a print(renvoieun()) print(a) Pour les listesL=est uneaectationet donc, dans une fonction, cree unLlocal, en re- vanche,L[i]=ouL[i:j]=ouL.append()sont desmodications. Enn le+=est vraiment a deconseiller pour les listes car son comportement est assez subtil.

Exemple a mediter :

def essaimodif(L):

L=L+[0]

return L

L=[1,2,3]

print(essaimodif(L)) print(L) Commentaire :Commentez le resultat obtenu puis ecrire une fonctionvraimodifqui fait vraiment ce qu'on aimerait qu'essaimodiffasse.

1.3 Une fonction peut appeler une autre fonction et m^eme renvoyer une

autre fonction! a) Pour le premier point, vous le savez bien. Si vous avez cree une fonction qui resout un probleme, vous pouvez vous en servir a l'interieur d'une autre.C'est m^eme une recommandation utile pour vos devoirs ecrits : utilisez les fonctions que vous avez deja denies! b) Le deuxieme point est peut-^etre plus surprenant pour l'instant, voyons un exemple mettant en valeur l'usage de fonctionslambda:1.let f x : x*x;; 2 def f_additionneur(n): """ renvoie la fonction x-> x+n""" return lambda x: x+n f=f_additionneur(2) g=f_additionneur(3) print(f(5)) print(g(5))

Que donnent les deuxprint?

2 Nouveaute : une fonction peut s'appeler elle-m^eme

2.1 Denition et parallelisme avec la recurrenceDenitionUnefonction recursiveest une fonctionftelle que le code de denition def

contienne un (ou plusieurs) appel(s) af. Ces appels sont appelesappels recursifs.Comme on va le voir dans les exemples ci-dessous, cette methode de denition de fonction est

tres proche de la notion dedenition par recurrenceen maths.

Exemple 1 :En maths, on peut denir la factorielle d'un entiern?Npar⎧⎪⎪⎨⎪⎪⎩0!=1;

?n?N?; n!=n×(n-1)! Une def. recursive de la factorielle enPython, calquee sur la def. mathematique precedente, est la suivante : def fact(n): if n==0 : return 1 else : return n*fact(n-1) Remarque :On utilise la m^eme syntaxe de def. de fonctions : il n'y pas de declaration particuliere pour les fonctions recursives (important pour les habitues a Caml). Exemple 2, exercice :(i) Si(un)est denie par rec. par⎧⎪⎪⎨⎪⎪⎩u 0=0; ?n?N;un+1=⎷2+un, denir une fonctionrecursiveuenPythonqui renvoie la valeuru(n)=unpour toutn?N. (ii)Experimentation :Que se passe-t-il si on veut calculeru1000? (iii) Calculeru1000a l'aide d'un algorithmeiteratif(boucle).

2.2 Comment ca marche une fonction recursive?

Un schema intuitif

On peut schematiser les operations faites pour le calcul defact(3)comme suit :1.2Pr ofondeurdepile Afindepr otég erlesystèmecontrelasaturation mémoir eengendréeparlesboucles infinies,Pythonestm unid"uneprot ection simple.Lenombremaximald "appelsrécursifs autoriséparunemêmefon ction estlimit é.C eparamètrelimites"ap pellela profondeurde pile,etv aut 1000danslesinstallationsPyt honstandard.

Consolepython

1>>>importsys

2>>>sys.getrecursionlimit()

31000
Celasignifiesimplementqu "unefoncti onrécursiv enepeut pass"appelerplusde1000fois. C"estun paramètrerég lableparlacomman desys.setrecursionlimit().Ainsi,l "appel desfonc tionsprécédentes,r1()our2(),condu itsystématiqueme ntaumessaged"erreur

RuntimeError:maximum recursiondepthexceeded.

Exercice1

Fixerlalimite del apileà10.Créer une fonctionrécursivequi afficheuncomp- teurpermettantdev érifierquel"erreurseproduit aubout du10 e appel.

Réponse1

1.3Les 3règlesdela progra mmationrécursive

Pouréviterqu"unefon cti onrécursivenefinisseenbou cleinfinie,elledoittoujoursp ossé- derun econditiond"arrêtinévi tablementdéclenchéeparuntest. Defaçongéné rale,tr oispropriétéssontàrespecterpou rs"assurerdu bonfonctionnement d"unefonctionrécursive: -elle doitconteniru ncasdebase; -elle doitmodifiersonéta tpourpouv oirserameneraucasde base; -elle doits"appelerelle-même. Vérifionscettedéfinitio ndanslecas delafonctionfactorielle n!=

1sin=0

n!(n"1)!sin#1 Onconstatebie niciquelecasdeb aseexiste,0!=1,que lafonctionmodifiesonétat parla relation(n"1)et s"appelleelle-même,(n"1)!. Implémentésousformerécursive, lafac toriellenécessitel "utilisationdelacommande returnquidoitren voy eràl"étageprécédentlavaleurcalculée.

Consolepython

1>>>deffact(n):

2...ifn==0:

3...return1

4...else:

5...returnn*fact(n-1)

Consolepython

1>>>fact(5)

2120
Ledérou lementdesopérationsnécessaire ses tprésen téci-après.Ilyadiminu tionpro- gressivedelavaleuràcalculer ,lorsdela" descente», jusqu"àarriverau casdebase ,qui déclenchealorsla" remon tée»desv aleursducontextepourdonnerlavaleurfinale.

FIGURE1-F actoriel lerécursive

Exercice2

Implémenteruneversionité rati vedelaf onctionfactorielle.

Réponse2

2Diff érentstypesderécursivité

Ils"agitsurt outdeciter lesdifférentessituationsde récursiv itéquiexistent .Le sdéfinitions

parlentd"elles-mêmes. 2/73

La gestion informatique de ce schema

Lorsqu'on appellefact(3), dans l'espace memoirelocalde la fonction, on denitn=3, leelse s'execute et donc voudrait executer lereturn 3*fact(2). Mais cette execution est dieree car pour executer cereturn, on doit d'abord appelerfact(2). Se cree alors un nouveau sous-espace memoire dedie a l'appel de cette fonctionfactavec une variable localen=2dans laquelle va s'executefact. Pendant toute la phase dedescentedu schema precedent, on cree doncquatre espaces de va- riables localesqu'on nommera ici espace 3,2,1,0, avec des variables locales correspondantes qu'on indicera par le numero de l'espace correspondantn3=3;:::;n0=0.

Dans l'espace 0, on peut calculerfact(0).

Avec cette valeur, on peut enn executer lereturn 1* fact(0)dans l'espace 1 et ainsi de suite. Comment rendre ce deroulement explicite a l'aide d'un script? def fact(n): if n==0 : return 1 else : print('--'*n+'> appel de fact',n-1) resultat=n*fact(n-1) # on a separe le calcul du return pour permettre l'affichage #de la ligne suivante print('--'*n+'> retour de fact',n-1) return resultat

Qui donne pourfact(3):

------> appel de fact 2 ----> appel de fact 1 --> appel de fact 0 --> retour de fact 0 ----> retour de fact 1 ------> retour de fact 2 Exercice :a)Commentez la place des deux instructions,printpar rapport aux deux autres lignes (appel et retour). b) Que donnerait le script suivant pourfact(3)? def fact(n): assert n >=0 if n==0 : return 1 else : resultat=n*fact(n-1) print('--'*n+'-> appel de fact',n-1) print('--'*n+'-> sortie de fact',n-1) return resultat

2.3 Points importants a retenir pour une fonction recursive

Ce que dit le lien avec les recurrences mathematiques D'une facon generale, deux proprietes sont a respecter pour s'assurer du bon fonctionnement d'une fonction recursive : | elle doit contenirun cas de base; | elle doit s'appeler elle-m^eme,en modiant son etat, pour pouvoirse ramener au cas de base. 4 La modication de l'etat est une modication d'au moins un des arguments de la fonction.

Dans l'exemple de la fonctionfact, on a :

| Un cas de basefact(0)=1; | un appel afact(n-1)qui va de proche en proche nous ramener afact(0).

Ce que dit la gestion informatique de la memoire

Une fonction recursive peut rapidement devenir tres gourmande en memoire! Exemple :Le calcul deu1000plus haut donne2le message d'erreur :

RuntimeError: maximum recursion depth exceeded

Le modulesysdePythonpermet de regler lenombre maximum d'appels recursifs autorise. Par defaut ce nombre est de 1000 comme en temoignent les instructions : import sys sys.getrecursionlimit()

On peut bien s^ur modier cette limite avec :

sys.setrecursionlimit(2000) Une fonction recursive risque de ne pas s'arr^eter

Que se passe-t-il si on appellefact(-1)?

En fait elle s'arr^ete gr^ace a ....

Mais on est dans un cas d'erreur du programme. On peut utiliser la commandeassertqui permettra de detecter tout de suite l'erreur, mais ce genre de chose n'est pas exigible au concours. def fact(n): assert n >=0 if n==0 : return 1 etc Alorsfact(-1)provoquera uneAssertionError. On peut m^eme rajouter un message pour preciser l'erreur 3

3 Versions recursives d'algorithmes vus en premiere annee

C'est aussi l'occasion de reviser des algo. qu'il faut savoir mettre en oeuvre!

3.1 L'algorithme d'Euclide

En premiere annee, on a etudie l'algo. d'Euclide pour trouver le pgcd de deux entiers naturels aetb.Une version recursive de cet algorithme : def Euclide2(a,b): if b==0 : return a else : return Euclide2(b,a%b)2. a condition de ne pas utiliser Ipython

3. Avec la syntaxe :assert n>=0, 'Attention n doit ^etre positif'. Mais la gestion des erreurs n'est pas un

attendu du programme pour les concours. L'essentiel est que vos fonctions marchent pour les entrees pour lesquelles

elles sont prevues. 5 Question 1 :A l'aide ou bien de vos souvenirs de premiere annee, ou bien de l'algo. ci-dessus, redonner une versioniterative(bouclewhile) pour ce m^eme algo.quotesdbs_dbs28.pdfusesText_34

[PDF] seuil de rentabilité cours pdf

[PDF] méthode des couts variables exercices corrigés

[PDF] exercice seuil de rentabilité corrigé pdf

[PDF] levier opérationnel calcul

[PDF] représentation graphique du seuil de rentabilité

[PDF] calcul du seuil de rentabilité avec plusieurs produits

[PDF] indice de sécurité calcul

[PDF] exercice seuil de rentabilité bts

[PDF] choix d'investissement exercices

[PDF] rentabilité des investissements cours

[PDF] calcul drci+formule

[PDF] calcul de rentabilité d'un investissement industriel

[PDF] etude de rentabilité d'une entreprise

[PDF] ratio de rentabilité commerciale

[PDF] rentabilité financière d'une entreprise