•ommaire• Introduction« Objets récursifs• Méthodes récursives

• Divide & Conquer

• Principe d'exécution

• Arbre d'exécution

• Preuve de terminaison

© L. H. Riundbane; FSM.TN

BJETS RECURSIFS (1)II est parfois difficile de définir un objet directement

II est plus simple de définir cet objet en fonctionde lui-mêmeExemple - chaîne de caractères

a) Classique : Une chaîne de caractères est une suite decaractères

b) Récursive : Une chaîne de caractères est soit la chaînevide; soit un caractère suivi d'une chaîne de caractère

6 L. B. Romdhane; FSM.TN

© L. B. Romdhane, Ph.D.

DSI / FSM / UM / Tunisie

• John McCarthy (MIT / Stanford)

• Algolôo ( ancêtre de Pascal, PL/1 et C)

• Lisp : structures de données et traitements récursifs

• Implémentation en langage de programmation

• au début : certains n'implémentait pas ce concept(COBOL, Fortran)

• actuellement : tous les langages

* Objets (structures de données) récursives* Méthodes (procédures et fonctions) récursives

L. B.Romdhanc; FSM.TN

OBJETS RECURSIFS (2)• Objet récursif: le nombre de composantess (objets) est

illimité ?

• La nécessité d'un point d'appui

• un objet particulier permettant de limiter le nombre

d'objets dans la définition

• Objet récursif :

• soit un objet particulier;

• soit une composante + un objet récursif

> L. B. Runidliane; FSM.TN

-T5ÎVÎDE & CONQUER'{2)1. Diviser : si la taille du problème est inférieur à un

certain seuil, alors le résoudre directement en allant

chercher parmi un ensemble de cas particuliers sinon

le diviser en un ensemble de sous-problèmes

2. Régner : Résoudre récursivement les sous-

problèmes selon le même principe

3. Combiner : les solutions des sous-problèmes pour

constituer la solution du problème original

ASI) i !.. B, Rumdhane; FSM.TN

-T5MDE&CONQUER(1)0 Diviser pour régner : un p r i n c i p e l n n d . u n r n i . i l p n n r

résoudre des problèmes informatiques COmplexei

• Idée- résoudre un problème S(n) de / < / ! / / < • u m Irdivisant en plusieurs sous-problèmes de même n . i i n i vS(n}, S(n-), ..., S(nk) telque(n,< n); V\\s e o m l u n nles solutions pour obtenir celle de S(n)

• La notion de taille dépend de la nature du prob lème !• Tri : le nombre d'éléments à trier• Factoriel : la valeur de l'entier

• Constitue le principe fondamental de la récursivité

I L. B. Romdhane; FSM.TN

"tfJVÎDE & CONQÛÏRlITAlgorithme Solve (I)

Débutn<- taille(I)

Si (n < seuil) alors solution <- directlySolve(I)

Sinon« diviser / en It, I 2 , ..., Ik

• Pour i de i à k faireS,<-Salvf:(I}

Fin Pour• Solution <— combiner^,,..., Sk )

Fin Si

Fin.

© L. B. Rumiihani-i FSM.TN

'MÉTHODES RECURSÎVES (1)j\ Une méthode est dite récursive, si elle fait appel à

elle-mêmeMéthode myRecursMethod ( ListeParam )

Environment

Début:

myRecursMethod ( ListeParam)

Fin.

« Nécessité d'une condition d'arrêt qui sera vraie à uninstant ultérieur de l'exécution

«5 L. M. Ruiiiiilitinc; KSM.TN

-METHODES RECURSIVES (3)• Environnement d'une méthode contient les

informations suivantes :• variables locales & paramètres de la méthode

• variables locales du compilateur

• @ de retour dans la méthode appelante; etc.

• Les appels à une méthode sont stockés dans une piled'exécution (frame stack)• Empiler un nouveau environnement par appel récursif

• Dépiler si la méthode s'est terminée

AS1> iO L. B, Roruiihane; FSM.TN

La suite de Fibonacci fonction fibo ( In n : entier)entier

• Un = U^ + Un.z VAR

fi, fa, f : entierDébut

• Ui = i; Uo = o

, . 1 Si ((n = o) OU (n=i))directlySolve(n) : .............,.,,,.„„_ a!ors f <_ n

1. Diviser2. Régner

3. Composer j"

sinonfi (— fibo (n -i)h <— fibo (n -2)

Fin Siretourner (f )Fin.

L. B. Romdliane; FSM.TN

Algorithme CalcFib

VAR X : entier

Début

X <- fibo (3)Fin.fonction ilbo( in n : entier) : entier

VAR fl, G, f: entier

Début

1. Si (n = 0)OU(n=l)

2. ulvrs f <— n

3. sîiiun

4. f 1 <- fibo (n -1)

5. f2 «- fibo (n -2)

6. f*- f l+f2

FiiiSi

7. retourner (f)

Fin.

RCrjRST\7fs4)? : "valeur indéfinie"

11:3

AS!) ) L. B. Romilhane; FSM.TN

fibo

f z : ?@ : ligne imainx : ?

fibon : 2fi:?

fi:?

@ : ligne i, 4fibon:3

£2:?fi;?f:?

main

-^IViETHODES RECURSIVESfibo <dn :i

f a : ?

fi:?

f : ?

@ : ligne i

fibon :a

f a : ?

fi: ?

f :?@ : ligne 4fibon:3

f a : ?

fi: ?

f :?

@ : ligne 4main

x:?

D fibo <jn : i

f z : ?

fi:?

f :i

@ : ligne 2

fibo

n : 2f a : ?

fi:?f : ?

@ : ligne 4fibo11:3£2: ?

fi:?f :?

@ : ligne 4

mainx : ?

fibo <jn : i

fa : ?

fi: ?

f : i@ : ligne 7

fibo

n :2

fa :?

fi:?f : ?

@ : ligne 4fibon:3

f a : ?

fi : ?

f : ?

@ : ligne 4mainx : ?

fibo <;

n : 2fa : ?

fi: if : ?

@ : ligne 5fibon: 3

fa : ?

fi : ?

f : ?

(!$ : ligne 4niai n

x : ?

fibo <fn : o

fa :?

fi:?

f : ?

@ : ligne ifibon ; 2

f a : ?

finf : ?

@ : ligne 5fibo11:3f a : ?

fi:?f :?

@ : ligne 4

main

x: ?

i L. B. Roimihanc; FSM.TN

-IViÉTHODES RECURSWËS (7)

fibo Cn : if z : ?

fi:?

f

@ : ligne

i

2,7

fibon:3

f a : ?

fi : i

f : ?

@ : ligne 5main

x : ?

fibon: 3

f a : i

Mfi: if : a

@ : ligne 6, 7main

x: ?

3 (^

mam <

x: .

L. B. Romdhane; ESM.TN

-"-IVTÉTHODES RECURSIVES(6)fibo Cqn : o

fa:?fi;?

f : o

@ : ligne 2

fibon : 2

h: ?fi :if : ?

@ : ligne gfibon:3

fa : ?

f i :?f : ?

@ : ligne 4mainx : ?

^ fibo <^n : o

f a : ?fi:?

f : o

@ : ligne 7

fibon : 2f a : ?

fi:i

f :?@ : ligne 5fibo

n:3

f a : ?fi:?f : ?

@ : ligne 4main

x : ?

u

fibo A\J-

n : 2

fa :ofi:i

f :i@ : ligne 6, 7fibon:3

fa :?fi: ?f :?

@ : ligne 4main

x : ?

zî

fibo

11:3fa : ?

£fi:if : ?

@ : ligne 5main

x: ?

^

fibo ç

n:i f i :?fz : ? f : ?@ : ligne ifibon:3 fi:ifa : ? f : ?

@ : ligne 5main

x: ?

L. B. Romdliane; FSM.TN

DE RECURSIVITË (1)• On distingue les types de récursivité suivants• Linéaire

• une méthode s'auto-appelle une seule fois• factoriel, puissance

• Binaire• une méthode s'auto-appelle une seule fois

• fibonacci

• Multiple• une méthode s'auto-appelle plus que deux fois

© L. B. Romdhane; FSM.TN

"TYPES DE RECURSIVITE (2)Factoriel (n) Puissance (x, n)

fonction factoriel(n : entier) :entierVAR f : entier

Débutsi (n=o) alors f f- o

sinon f <-- n * factoriel (n-i)

fin Si

retourner (f )Fin.

~Joncnôn pulssahcefx: réel, n : entier) :réel

VAR r : r ée lDébut

ïi (n=o) alors r «— ii'inon

MOD 2.) -o alors*— pul6fiance(Xj n DIV z)<— r * r

pulsuncefo (n -0 DIV 2)- K * r * r

fin Sifin Si

retourner (r)lin.

10 L. U. Kuimiliiuic; KSM.1N

A chaque nœud de l'arbre, on représente l'ensembledes paramètres de l'appel récursif, la taille du problème,

etc.

La racine est constitué du premier appel à la méthode

Chaque appel récursif est représenté dans un nœud filsdu nœud où l'appel a été engendré

Les nœuds terminaux (ou feuilles) n'engendrent aucun

appel récursif• Ils représentent les cas de base (où la taille du problème

est inférieur au seuil critique)

ASD © L. B. Romdhane ; (SM.TN

DE LA RECURSIVITE (1)A\ L'exécution d'une méthode récursive peut êtPe

modélisée à l'aide d'un arbre• un ensemble de nœuds; et de liens (parent / fils)

• et une racine

• Utilité ?

1. une meilleure compréhension du déroulement

2. un outil formel pour analyser le coût d'exécutiond'une méthode récursive

© L. B. Romdhane; FSM.TN

DE LA RECURSIVITE (3)

C L, B. Romdhime; FSM.TN

"ARBRE DE LA REÇURSIVITE (4)• Une fois construit, cet arbre fournit un outil

mathématique pour analyser le coût d'exécution d'uneméthode récursive

• Calculer le coût à chaque appel; puis sommer sur tousles nœuds de l'arbre

• coût total est fonction• du nombre de nœuds (nombre d'appels)• Le coût à chaque nœud (appel)

O !.. H. K dhane; KSM.TM

ARBRE DE LA RECURSIVITE (5)

• coût: nombred'opérations d'ajjlftkm &d'affectation• coût total = 9

• Quel serait le coût pourfibo (n) d'une manièregénérale ?

fibo (3) 13]

fibo-U) j 3 j fibo (i) j

2 >

G L. B. Romdhane; FSM.TN

"DISCUSSION -TERMINAISON• Une méthode récursive finit-elle toujours par s'arrêter

lorsqu'elle est exécutée sur un jeu de données biendéterminée ?

» Un problème non-décidable !8 Aucune preuve formelle

• Généralement, on fait appel au « bon sens »• vérifier que la taille du sous-problème est inférieur à la

taille du problème original avant l'appel récursif> vérifier les conditions d'exécution avant de lancer l'appel

récursif

O L. B. Rimidhane; VSM.TN

L'exactitude d'une méthode récursive est faitegénéralement par induction ^ -~ —""•-

Soit P(n) une proposition dont on veut démontrerl'exactitude

Démontrer que P(n) est vraie Vne W] où 14/estunensemble de cas de base connus

Exprimer P(n) en fonction de P(n), ..,, P(nk); où n( < n

Supposer que P(n),..., P(nk); sont vraies; et

Démontrer que P(n) est vraie

© L. B. Roindhane; FSM.TN