[PDF] Programmation fonctionnelle Récursivité

View - Download Programmation fonctionnelle Récursivité

Previous PDF

Next PDF

Programmation fonctionnelle

Notes de cours

Cours 3bis

3 Octobre 2012

Sylvain Conchon

sylvain.conchon@lri.fr

1/29R´ecursivit´e

2/29D´efinitions r´ecursives

Une fonction est

r ´ecursive s ielle fait app el` aelle m ˆemedans sa propre d´efinitionPar exemple, la fonction factoriellen! peut ˆetre d´efinie de mani`ere r´ecursive, pour tout entiern, par les deux ´equations suivantes

0! = 1

n!= n×(n-1)!

3/29Fonctions r´ecursives enOcaml

La d´efinition d"une fonction r´ecursive est introduite par l"adjonction du mot cl´erecau mot cl´elet let rec fact n = if n=0 then 1 else n * fact (n-1) 4/29

Avantages des d´efinitions r´ecursives

L"´ecriture `a l"aide d"une fonction r´ecursive donne souvent un code plus lisible et plus susceptible d" ˆetre co rrect (ca rd"inva riantplus simple) que son ´equivalent imp´eratif utilisant une boucle int fact(int n){ int f = 1; int i = n; while (i>0){ f = f * i; i--; return f; l"argument justifiant la correction de cette version est nettement plus complexe que la version r´ecursive

5/29Processus d"´evaluation

let rec fact n = if n=0 then 1 else n * fact (n-1)

fact 33?= 0?3 *fact(3-1) 2?= 0?3 * 2 *fact(2-1) 1?= 0?3 * 2 * 1 *fact(1-1) 0 = 0?3 * 2 * 1 *1 ?3 * 2 * 1?3 * 2?66/29Processus d"´evaluation

let rec fact n = if n=0 then 1 else n * fact (n-1)

fact 33?= 0?3 *fact(3-1) 2?= 0?3 * 2 *fact(2-1) 1?= 0?3 * 2 * 1 *fact(1-1) 0 = 0?3 * 2 * 1 *1 ?3 * 2 * 1?3 * 2?66/29Processus d"´evaluation

let rec fact n = if n=0 then 1 else n * fact (n-1)

fact 33?= 0?3 *fact(3-1) 2?= 0?3 * 2 *fact(2-1) 1?= 0?3 * 2 * 1 *fact(1-1) 0 = 0?3 * 2 * 1 *1 ?3 * 2 * 1?3 * 2?66/29

Processus d"´evaluation

let rec fact n = if n=0 then 1 else n * fact (n-1)

fact 33?= 0?3 *fact(3-1) 2?= 0?3 * 2 *fact(2-1) 1?= 0?3 * 2 * 1 *fact(1-1) 0 = 0?3 * 2 * 1 *1 ?3 * 2 * 1?3 * 2?66/29Processus d"´evaluation

let rec fact n = if n=0 then 1 else n * fact (n-1)

fact 33?= 0?3 *fact(3-1) 2?= 0?3 * 2 *fact(2-1) 1?= 0?3 * 2 * 1 *fact(1-1) 0 = 0?3 * 2 * 1 *1 ?3 * 2 * 1?3 * 2?66/29Processus d"´evaluation

let rec fact n = if n=0 then 1 else n * fact (n-1)

fact 33?= 0?3 *fact(3-1) 2?= 0?3 * 2 *fact(2-1) 1?= 0?3 * 2 * 1 *fact(1-1) 0 = 0?3 * 2 * 1 *1 ?3 * 2 * 1?3 * 2?66/29Processus d"´evaluation

let rec fact n = if n=0 then 1 else n * fact (n-1)

fact 33?= 0?3 *fact(3-1) 2?= 0?3 * 2 *fact(2-1) 1?= 0?3 * 2 * 1 *fact(1-1) 0 = 0?3 * 2 * 1 *1 ?3 * 2 * 1?3 * 2?66/29

Processus d"´evaluation

let rec fact n = if n=0 then 1 else n * fact (n-1)

fact 33?= 0?3 *fact(3-1) 2?= 0?3 * 2 *fact(2-1) 1?= 0?3 * 2 * 1 *fact(1-1) 0 = 0?3 * 2 * 1 *1 ?3 * 2 * 1?3 * 2?66/29Que se passe-t-il sinest n´egatif?

1.n!est d´efinie surN

2. la fonction facta pour typeint→intetne termine pas si

son param`etre est n´egatifQuellevaleur factpeut-elle rendre sin<0?La seule solution raisonnable est destopperle calcul en cours et

d"expliquerle probl`eme `a l"utilisateur On utilise pour cela la fonction pr´ed´efiniefailwithmqui termine un programme en affichant le messagem`a l"´ecran7/29Que se passe-t-il sinest n´egatif?

1.n!est d´efinie surN

2. la fonction facta pour typeint→intetne termine pas si

son param`etre est n´egatifQuellevaleur factpeut-elle rendre sin<0?La seule solution raisonnable est destopperle calcul en cours et

d"expliquerle probl`eme `a l"utilisateur On utilise pour cela la fonction pr´ed´efiniefailwithmqui termine un programme en affichant le messagem`a l"´ecran7/29Que se passe-t-il sinest n´egatif?

1.n!est d´efinie surN

2. la fonction facta pour typeint→intetne termine pas si

son param`etre est n´egatifQuellevaleur factpeut-elle rendre sin<0?La seule solution raisonnable est destopperle calcul en cours et

d"expliquerle probl`eme `a l"utilisateur On utilise pour cela la fonction pr´ed´efiniefailwithmqui termine un programme en affichant le messagem`a l"´ecran7/29

Fonctionfact(deuxi`eme version)

let rec fact n = if n<0 then failwith "argument negatif" else

if n=0 then 1 else n * fact (n-1)Encore mieux, une fonction interm´ediaire pour ´eviter des tests

inutiles let rec factorielle n = if n=0 then 1 else n * factorielle (n-1) let fact n = if n<0 then failwith "argument negatif" else factorielle n

8/29Fonctionfact(deuxi`eme version)

let rec fact n = if n<0 then failwith "argument negatif" else

if n=0 then 1 else n * fact (n-1)Encore mieux, une fonction interm´ediaire pour ´eviter des tests

inutiles let rec factorielle n = if n=0 then 1 else n * factorielle (n-1) let fact n = if n<0 then failwith "argument negatif" else factorielle n

8/29Fonctionfact(troisi`eme version)

On peut cacher la fonction "incorrecte" comme une fonction locale let fact n = let rec factorielle n = if n=0 then 1 else n * factorielle (n-1) in if n<0 then failwith "argument negatif" else factorielle n

9/29D´efinitions par cas

Analyse par cas d"une valeur avec la constructionmatch-with let rec fact n = match n with

0 -> 1

| _ -> n * fact (n-1) Ceci permet de se rapprocher encore plus de la d´efinition math´ematique 10/29

La fonctionpuissance(1/3)

x 0= 1 x n=x?x(n-1)let rec puissance x n = match n with

0 -> 1

| _ -> x * puissance x (n-1)

11/29La fonctionpuissance(1/3)

x 0= 1 x n=x?x(n-1)let rec puissance x n = match n with

0 -> 1

| _ -> x * puissance x (n-1)

11/29La fonctionpuissance(2/3)

Une version plus rapide qui exploite la parit´e den x 0= 1 x

2n=xn?xn

x

2n+1=x?xn?xnlet rec puissance x n =

match n with

0 -> 1

| 1 -> x | _ -> let e = puissance x (n/2) in if n mod 2 = 0 then e*e else x * e * e

12/29La fonctionpuissance(2/3)

Une version plus rapide qui exploite la parit´e den x 0= 1 x

2n=xn?xn

x

2n+1=x?xn?xnlet rec puissance x n =

match n with

0 -> 1

| 1 -> x | _ -> let e = puissance x (n/2) in if n mod 2 = 0 then e*e else x * e * e 12/29

La fonctionpuissance(3/3)

Encore une fois, pour ´eviter de boucler sur un argumentnn´egatif, on utilise une fonction "englobante" let puissance x n = let rec puissance n = match n with

0 -> 1

| 1 -> x | _ -> let e = puissance (n/2) in if n mod 2 = 0 then e*e else x * e * e in if n<0 then failwith "argument n´egatif" else puissance n

13/29´

Evaluation de la fonctionpuissance

puissance 4 5?let e = puissance 4 2 in 4 * e *e ?let e = (let e"= puissance 4 1 in e"*e") in 4 * e * e ?let e = (let e"= 4 in e"*e") in 4 * e * e ?let e = 4 * 4 in 4 * e * e ?let e = 16 in 4 * e * e ?4 * 16 * 16 ?1024

14/29´

Evaluation de la fonctionpuissance

puissance 4 5?let e = puissance 4 2 in 4 * e *e ?let e = (let e"= puissance 4 1 in e"*e") in 4 * e * e ?let e = (let e"= 4 in e"*e") in 4 * e * e ?let e = 4 * 4 in 4 * e * e ?let e = 16 in 4 * e * e ?4 * 16 * 16 ?1024

14/29´

Evaluation de la fonctionpuissance

puissance 4 5?let e = puissance 4 2 in 4 * e *e ?let e = (let e"= puissance 4 1 in e"*e") in 4 * e * e ?let e = (let e"= 4 in e"*e") in 4 * e * e ?let e = 4 * 4 in 4 * e * e ?let e = 16 in 4 * e * e ?4 * 16 * 16 ?1024 14/29

Evaluation de la fonctionpuissance

puissance 4 5?let e = puissance 4 2 in 4 * e *e ?let e = (let e"= puissance 4 1 in e"*e") in 4 * e * e ?let e = (let e"= 4 in e"*e") in 4 * e * e ?let e = 4 * 4 in 4 * e * e ?let e = 16 in 4 * e * e ?4 * 16 * 16 ?1024

14/29´

Evaluation de la fonctionpuissance

puissance 4 5?let e = puissance 4 2 in 4 * e *e ?let e = (let e"= puissance 4 1 in e"*e") in 4 * e * e ?let e = (let e"= 4 in e"*e") in 4 * e * e ?let e = 4 * 4 in 4 * e * e ?let e = 16 in 4 * e * e ?4 * 16 * 16 ?1024

14/29´

Evaluation de la fonctionpuissance

puissance 4 5?let e = puissance 4 2 in 4 * e *e ?let e = (let e"= puissance 4 1 in e"*e") in 4 * e * e ?let e = (let e"= 4 in e"*e") in 4 * e * e ?let e = 4 * 4 in 4 * e * e ?let e = 16 in 4 * e * e ?4 * 16 * 16 ?1024

14/29´

Evaluation de la fonctionpuissance

puissance 4 5?let e = puissance 4 2 in 4 * e *e ?let e = (let e"= puissance 4 1 in e"*e") in 4 * e * e ?let e = (let e"= 4 in e"*e") in 4 * e * e ?let e = 4 * 4 in 4 * e * e ?let e = 16 in 4 * e * e ?4 * 16 * 16 ?1024 14/29

Evaluation de la fonctionpuissance

puissance 4 5?let e = puissance 4 2 in 4 * e *e ?let e = (let e"= puissance 4 1 in e"*e") in 4 * e * e ?let e = (let e"= 4 in e"*e") in 4 * e * e ?let e = 4 * 4 in 4 * e * e ?let e = 16 in 4 * e * e ?4 * 16 * 16 ?1024

14/29Ensemble de Cantor

D´efinir une fonction Cantor qui ´etant donn´e un entiernd´ecide si, dans l"´ecriture en base 3 (´ecriture qui utilise les chiffres 0, 1 et 2), ns"´ecrit en utilisant uniquement des 0 et des 1let rec cantor n = match n with

0 -> true

| _ -> if n mod 3 = 2 then false else cantor (n / 3)ou plus simplement let rec cantor n = (n=0) || (n mod 3 <>2 && cantor (n/3))

15/29Ensemble de Cantor

D´efinir une fonction Cantor qui ´etant donn´e un entiernd´ecide si, dans l"´ecriture en base 3 (´ecriture qui utilise les chiffres 0, 1 et 2), ns"´ecrit en utilisant uniquement des 0 et des 1let rec cantor n = match n with

0 -> true

| _ -> if n mod 3 = 2 then false else cantor (n / 3)ou plus simplement let rec cantor n = (n=0) || (n mod 3 <>2 && cantor (n/3))

15/29Ensemble de Cantor

D´efinir une fonction Cantor qui ´etant donn´e un entiernd´ecide si, dans l"´ecriture en base 3 (´ecriture qui utilise les chiffres 0, 1 et 2), ns"´ecrit en utilisant uniquement des 0 et des 1let rec cantor n = match n with

0 -> true

| _ -> if n mod 3 = 2 then false else cantor (n / 3)ou plus simplement let rec cantor n = (n=0) || (n mod 3 <>2 && cantor (n/3)) 15/29

R´ecursivit´e double

R´ecursivit´e double :

plusieurs app elsr ´ecursifsp euventappa raˆıtre dans la d´efinitionlet rec fibonacci n = match n with

0 -> 0

| 1 -> 1 | _ -> fibonacci (n-1) + fibonacci (n-2)

16/29R´ecursivit´e double

R´ecursivit´e double :

plusieurs app elsr ´ecursifsp euventappa raˆıtre dans la d´efinitionlet rec fibonacci n = match n with

0 -> 0

| 1 -> 1 | _ -> fibonacci (n-1) + fibonacci (n-2)

16/29R´ecursivit´e mutuelle (1/2)

R´ecursivit´e mutuelle :

Une fon ctionfpeut faire r´ef´erence `a une

fonctiongqui elle-mˆeme fait r´ef´erence `af pair.ml let rec pair n = (n = 0) || impair (n-1) let rec impair n = (n <> 0) && pair (n-1)compilation > ocamlc -o pair pair.ml

File "pair.ml", line 1, characters 28-34:

Unbound value impair

17/29R´ecursivit´e mutuelle (1/2)

R´ecursivit´e mutuelle :

Une fon ctionfpeut faire r´ef´erence `a une

fonctiongqui elle-mˆeme fait r´ef´erence `af pair.ml let rec pair n = (n = 0) || impair (n-1) let rec impair n = (n <> 0) && pair (n-1)compilation > ocamlc -o pair pair.ml

File "pair.ml", line 1, characters 28-34:

Unbound value impair

17/29

R´ecursivit´e mutuelle (2/2)

Pour d´efinir deux fonctionsfetgmutuellement r´ecursives on utilise la construction let rec f = e1 and g = e2 pair.ml let rec pair n = (n = 0) || impair (n-1) and impair n = (n <> 0) && pair (n-1)

18/29Principes d"une d´efinition r´ecursive

L"analyse par cas dans une d´efinition r´ecursive permet de regrouper les cas de base non r´ecursifs les cas r ´ecursifs qui renvoient ` ala d ´efinitionen cours La d´efinition d"une fonction r´ecursive revient toujours ` aidentifier

ces diff´erents cas puis `a v´erifier que :1.Les cas r ´ecursifsfinissent pa rrenvo yeraux cas de base (afin

de garantir la terminaison de la fonction)2.T ousles cas sont couverts dans la d ´efinition 3. On ne risque pas de b ouclersur des cas r ´ecursifs,en s"assurant par exemple que chaque appel r´ecursif renvoie `a un casplus simple19/29Principes d"une d´efinition r´ecursive L"analyse par cas dans une d´efinition r´ecursive permet de regrouper les cas de base non r´ecursifs les cas r ´ecursifs qui renvoient ` ala d ´efinitionen cours La d´efinition d"une fonction r´ecursive revient toujours ` aidentifier

ces diff´erents cas puis `a v´erifier que :1.Les cas r ´ecursifsfinissent pa rrenvo yeraux cas de base (afin

de garantir la terminaison de la fonction)2.T ousles cas sont couverts dans la d ´efinition 3. On ne risque pas de b ouclersur des cas r ´ecursifs,en s"assurant par exemple que chaque appel r´ecursif renvoie `a un casplus simple19/29Principes d"une d´efinition r´ecursive L"analyse par cas dans une d´efinition r´ecursive permet de regrouper les cas de base non r´ecursifs les cas r ´ecursifs qui renvoient ` ala d ´efinitionen cours La d´efinition d"une fonction r´ecursive revient toujours ` aidentifier

ces diff´erents cas puis `a v´erifier que :1.Les cas r ´ecursifsfinissent pa rrenvo yeraux cas de base (afin

de garantir la terminaison de la fonction)2.T ousles cas sont couverts dans la d ´efinition 3. On ne risque pas de b ouclersur des cas r ´ecursifs,en s"assurant par exemple que chaque appel r´ecursif renvoie `a un casplus simple19/29

Principes d"une d´efinition r´ecursive

L"analyse par cas dans une d´efinition r´ecursive permet de regrouper les cas de base non r´ecursifs les cas r ´ecursifs qui renvoient ` ala d ´efinitionen cours La d´efinition d"une fonction r´ecursive revient toujours ` aidentifier

ces diff´erents cas puis `a v´erifier que :1.Les cas r ´ecursifsfinissent pa rrenvo yeraux cas de base (afin

de garantir la terminaison de la fonction)2.T ousles cas sont couverts dans la d ´efinition 3. On ne risque pas de b ouclersur des cas r ´ecursifs,en s"assurant par exemple que chaque appel r´ecursif renvoie `a un casplus simple19/29Exemples de mauvaises d´efinitions r´ecursives

Probl`eme de

terminaison : les cas r ´ecursifsne renvoient pas aux cas de base let rec fibonacci n = match n with

0 -> 0

| _ -> fibonacci (n-1) + fibonacci (n-2)Probl`eme decouverture des cas p ossibles let mystere x = let rec mystere x n = match n with

0 -> 1

| 1 -> x * mystere (x/2) ((x mod 2)+n) in if x<=0 then 1 else mystere x 1

20/29Exemples de mauvaises d´efinitions r´ecursives

Probl`eme de

terminaison : les cas r ´ecursifsne renvoient pas aux cas de base let rec fibonacci n = match n with

0 -> 0

| _ -> fibonacci (n-1) + fibonacci (n-2)Probl`eme decouverture des cas p ossibles let mystere x = let rec mystere x n = match n with

0 -> 1

| 1 -> x * mystere (x/2) ((x mod 2)+n) in if x<=0 then 1 else mystere x 1

20/29R´ecursion infinie

Il arrive cependant parfois de vouloir ´ecrire de "mauvaises" d´efinitions r´ecursives Soit la fonctionzeroqui recherche (´eventuellement ind´efiniment) une valeur pour laquelle une fonctionfs"annule let zero f = let rec recherche i = if f i = 0 then i else recherche (i+1) in recherche 0 21/29
quotesdbs_dbs22.pdfusesText_28

[PDF] Corrigé Série d exercices n°4 : Les fonctions et procédures

[PDF] Bases d 'algorithmique

[PDF] COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE

[PDF] FICHE n°6 : PROGRAMMER DES BOUCLES - Maths-et-tiques

[PDF] fiche maternelle algorithme imprimer- pdf documents

[PDF] Fiche enseignant ALGORITHMES NIVEAU : GRANDE SECTION

[PDF] Algorithme et numération - Académie de Nancy-Metz

[PDF] L 'atelier des petites chenilles en PS Etape 1 - académie de Caen

[PDF] reproduire une suite algorithmique - Accueil DSDEN 22

[PDF] Rappels : Tableaux et Matrices

[PDF] N°96 - spécial mouvement intra 2016pub - Snes

[PDF] Algorithmique et programmation : les bases (Algo) Corrigé

[PDF] TP7 : le théor`eme du point fixe en action sous MATLAB

[PDF] Séance de travaux pratiques n° 1

[PDF] simulations, algorithmes en probabilités et statistique(s) au - Apmep