Récursivité

Click to add text

 Ordre du jour

Récursivité and Récurrence

Définitions Récursives
 Ensembles
 Chaînes de caractères
Algorithmes Récursifs

2
Définition récursive d’une suite
Il est souvent difficile d'exprimer les membres d'un
ensemble ou d'une suite numérique explicitement.
EG: La suite de Fibonacci:
{fn } = 0,1,1,2,3,5,8,13,21,34,55,…
Il se peut, cependant qu
’il y’a certaines relations qui peuvent donner lieu à
une définition récursive -une ​formule qui
exprime les termes d'ordre plus élevé, en fonction
de termes de plus bas ordre.
EG: Définition recursive de {fn }:
INITIALIZATION: f0 = 0, f1 = 1
3
 Définition récursive
et récurrence
Définition récursive et démonstration par récurrence
sont complémentaires: une définition récursive
donne généralement lieu à une preuve naturelle
impliquant la suite récurrente.
Ceci résulte de la forme d'une définition récursive
constituée de deux parties:
1. Initialisation -analogue à l’étape de base de
l’induction
2. Récurrence -analogue à l’étape de l’induction
Dans l'induction et la récursivité, l'analogie domino
est utile.
4
 Fonctions récursives
Il est possible de penser à une fonction de domaine
N comme une suite de nombres, et vice-versa.
Il suffit de poser: fn =f (n)
Par exemple, notre suite de Fibonacci devient la
fonction de Fibonacci définie comme suit:
f (0) = 0, f (1) = 1, f (2) = 1, f (3) = 2,…
Ces fonctions peuvent être définies de manière
récursive en utilisant la définition par récurrence de
la suite. EG:
INITIALIZATION: f (0) = 0, f (1) = 1
RECURSION: f (n)=f (n -1)+f (n -2), for n > 1.5
 Fonctions récursives
Factorielle
Un exemple simple d'une fonction récursive
définie est la fonction factorielle:
n! = 1· 2· 3· 4 ···(n –2)·(n –1)·n
i.e., le produit des n premiers nombres
positifs (par convention, le produit de rien,
c'est 1, de sorte que 0! = 1).
Q: Trouver une définition récursive de n!

6
 Fonctions récursives
Factorielle
A:INITIALISATION: 0!= 1
RECURSION: n != n · (n -1)!
Pour calculer la valeur d'une fonction récursive,
par exemple, 5 !, on se branche sur la définition
récursive pour obtenir des expressions
impliquant des valeurs d’ordre inférieurs de la
fonction, jusqu'à arriver au cas de l’initialisation.

EG: 5! =

7
 Fonctions récursives
Factorielle
A:INITIALISATION: 0!= 1
RECURRENCE: n != n · (n -1)!
Pour calculer la valeur d'une fonction récursive,
par exemple, 5 !, on se branche sur la définition
récursive pour obtenir des expressions
impliquant des valeurs d’ordre inférieurs de la
fonction, jusqu'à arriver au cas de l’initialisation.

récurrence
EG: 5! = 5 · 4!

8
 Fonctions récursives
Factorielle
A:INITIALISATION: 0!= 1
RECURRENCE: n != n · (n -1)!
Pour calculer la valeur d'une fonction récursive,
par exemple, 5 !, on se branche sur la définition
récursive pour obtenir des expressions
impliquant des valeurs d’ordre inférieurs de la
fonction, jusqu'à arriver au cas de l’initialisation.

récurrence
EG: 5! = 5 · 4! = 5 · 4 · 3!

9
 Fonctions récursives
Factorielle
A:INITIALISATION: 0!= 1
RECURRENCE: n != n · (n -1)!
Pour calculer la valeur d'une fonction récursive,
par exemple, 5 !, on se branche sur la définition
récursive pour obtenir des expressions
impliquant des valeurs d’ordre inférieurs de la
fonction, jusqu'à arriver au cas de l’initialisation.

récurrence
EG: 5! = 5 · 4! = 5 · 4 · 3! = 5 · 4 · 3 · 2!

10
 Fonctions récursives
Factorielle
A:INITIALISATION: 0!= 1
RECURRENCE: n != n · (n -1)!
Pour calculer la valeur d'une fonction récursive,
par exemple, 5 !, on se branche sur la définition
récursive pour obtenir des expressions
impliquant des valeurs d’ordre inférieurs de la
fonction, jusqu'à arriver au cas de l’initialisation.

récurrence
EG: 5! = 5 · 4! = 5 · 4 · 3! = 5 · 4 · 3 · 2!
= 5 · 4 · 3 · 2 · 1!
11
 Fonctions récursives
Factorielle
A:INITIALISATION: 0!= 1
RECURRENCE: n != n · (n -1)!
Pour calculer la valeur d'une fonction récursive,
par exemple, 5 !, on se branche sur la définition
récursive pour obtenir des expressions
impliquant des valeurs d’ordre inférieurs de la
fonction, jusqu'à arriver au cas de l’initialisation.

récurrence
EG: 5! = 5 · 4! = 5 · 4 · 3! = 5 · 4 · 3 · 2!
= 5 · 4 · 3 · 2 · 1! = 5 · 4 · 3 · 2 · 1 · 0!
12
 Fonctions récursives
Factorielle
A:INITIALISATION: 0!= 1
RECURRENCE: n != n · (n -1)!
Pour calculer la valeur d'une fonction récursive,
par exemple, 5 !, on se branche sur la définition
récursive pour obtenir des expressions
impliquant des valeurs d’ordre inférieurs de la
fonction, jusqu'à arriver au cas de l’initialisation.

EG: 5! = 5 ·récurrence
4! = 5 · 4 · 3! = 5 · 4 · 3 · 2!
= 5 · 4 · 3 · 2 · 1! = 5 · 4 · 3 · 2 · 1 · 0!
= 5 · 4 · 3 · 2 · 1 · 1 = 120
13
 Fonctions récursives
combinaison de k parmi n
Les coefficients binomiaux apparaissent dans
de nombreuses applications:
1) Combinatoire / Probabilité (k parmi n):
C (n,k) = le nombre de différents
groupes de taille k à partir d'un groupe
initial de taille n.
2) Algèbre:
C (n,k) = kième coefficient du terme
de l'expansion de la nième puissance du
binôme (x + y )n
 n
Notat couramment utilisée:C ( n, k )    14
 
 Combinaison de k parmi n
et le triangle de Pascal
Typiquement, le moyen le plus rapide pour
calculer tous les C (n,k) jusqu'à un certain
n est le triangle de Pascal. Dans le triangle
de Pascal, un 1 est mis en haut
(initialisation) et chaque élément est par
conséquent de manière récursive définit
comme étant la somme des nombres de
droite et celui de gauche dans la rangée
précédente. Si un nombre est manquant, il
est considéré comme étant 0.
15
Combinaison de k parmi n
et le triangle de Pascal
1

16
Combinaison de k parmi n
et le triangle de Pascal
1
1 1

17
Combinaison de k parmi n
et le triangle de Pascal
1
1 1
1 2 1

18
Combinaison de k parmi n
et le triangle de Pascal
1
1 1
1 2 1
13 31

19
Combinaison de k parmi n
et le triangle de Pascal
1
1 1
1 2 1
13 31
14 6 41

20
Combinaison de k parmi n
et le triangle de Pascal
1
1 1
1 2 1
13 31
14 6 41
1 5 10 10 5 1

21
Combinaison de k parmi n
et le triangle de Pascal
1
1 1
1 2 1
13 31
14 6 41
1 5 10 10 5 1
1 6 15 20 15 6 1

22
 Combinaison de k parmi n
et le triangle de Pascal
n = ligne 0 k = col. diagonale
0 1 1
1 1 1 2
2 1 2 1 3
3 13 31 4
4 14 6 4 15
5 1 5 10 10 5 1 6
6 1 6 15 20 15 6 1
Q: Trouver C (6,4)
23
 Combinaison de k parmi n
et le triangle de Pascal
n = ligne 0 k = col. diagonale
0 1 1
1 1 1 2
2 1 2 13
3 13 314
4 1 4 6 4 15
5 1 5 10 10 5 1 6
6 1 6 15 20 15 6 1
A:C (6,4)=15. Q: Comment former C(n,k) ?
24
 Combinaison de k parmi n
et le triangle de Pascal
A: Utilisation du triangle de Pascal.
INITIALIZATION: Sommet du triangle est 1.
D’où, C (0,0) = 1. Si un nombre est
manquant, il est considéré égal à 0. Ce qui
donne C (n,k) = 0 if k < 0, or k > n.
RECURRENCE: Élément suivant est la somme
des nombres à droite et à gauche de celui-ci
dans la ligne précédente:
C (n,k) = C (n -1,k) + C (n -1,k -1)

25
 Combinaison de k parmi n
et le triangle de Pascal
Un moyen standard d'exprimer des formules
récursives appliquées ci-dessus:
0, si k  0 or k  n

C (n, k )  1, si k  n  0
C (n  1, k  1)  C (n  1, k ), sinon

Q: Trouver une définition récursive de la
fonction pgcd.
Astuce: l'algorithme d'Euclide.

26
 Définitions récursives
pgcd
A: L'algorithme d'Euclide permet d'utiliser
le fait que pgcd(x,y ) = pgcd(y, x mod
y)

 x, if y  0
gcd( x, y )  
gcd( y, x mod y ), sinon
(Ici, on suppose que x > 0)

27
 Définitions récursives
et notations mathématiques
Définition de la notation de sommation :
0 , if n  0
n
 n 1
 ai  
i 1  ai  an , if n  0
 i 1
Il y’a aussi une notation générale du
produit : n
 ai  a1  a2  an1  an
i 1 n
Q: Trouver une formule simple pour  i
i 1
28
 Définitions récursives
et notations mathématiques
A: C'est encore la fonction factorielle:
n

 i  1 2  3  4 (n  1)  n  n!
i 1

Q: Trouver une définition récursive pour

la notation du produit
n

a
i 1
i

29
 Définitions récursives
et notations mathématiques
A: Ceci est très similaire à la définition de
la notation somme.
1, if n  0
n
 n 1
 ai   
i 1   ai   an , if n  0
 i 1 
Note: L'initialisation est l'argument de
"produit de rien» étant 1, pas 0.

30
 Algorithmes récursifs
Une fois que vous avez compris la
définition récursive d'une fonction, on
peut immédiatement transformer en un
algorithme récursif en language info.
(language MATLAB par ex.) qui peut
gérer la récursivité.
Considérons par exemple la fonction
factorielle n! :
1, if n  0
n! factorial(n)  
n  factorial(n  1), if n  0
31
 Algorithmes récursifs
Nous pouvons convertir immédiatement la
définition:
1, if n  0
n! factorial (n)  
into code: n  factorial (n  1), if n  0
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

Ensuite, nous laissons la machine virtuelle

MATLAB faire le reste, comme suit:
32
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

Calcul de 5!

33
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

f(5)=
5·f(4)

34
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

f(4)= f(5)=
4·f(3) 5·f(4)

35
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

f(3)= f(4)= f(5)=

3·f(2) 4·f(3) 5·f(4)

36
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

f(2)= f(3)= f(4)= f(5)=

2·f(1) 3·f(2) 4·f(3) 5·f(4)

37
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

f(1)= f(2)= f(3)= f(4)= f(5)=

1·f(0) 2·f(1) 3·f(2) 4·f(3) 5·f(4)

38
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

f(0)= f(1)= f(2)= f(3)= f(4)= f(5)=

1 1·f(0) 2·f(1) 3·f(2) 4·f(3) 5·f(4)

39
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

1·1= f(2)= f(3)= f(4)= f(5)=

1 2·f(1) 3·f(2) 4·f(3) 5·f(4)

40
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

2·1= f(3)= f(4)= f(5)=

2 3·f(2) 4·f(3) 5·f(4)

41
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

3·2= f(4)= f(5)=

6 4·f(3) 5·f(4)

42
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

4·6= f(5)=
24 5·f(4)

43
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

5·24=
120

44
 Algorithmes récursifs
Implémentation
factorial(n)
if (n<=0) return 1
return n*factorial(n-1)

Return 5!
= 120

45
 Des définitions récursives aux
algorithmes récursifs
En général, à partir d'une fonction récursive:
output1 , if n in range1

f ( n )  
output , if n in range
 k k
donne un algorithme récursif:
output f(n)
if (n in range1)
return output1
…
if (n in rangek)
return outputk
46
 Algorithmes récursifs
Exemples
Nous pouvons également tourner les
définitions récursives de la fonction de
Fibonacci, les coefficients du binôme et le
pgcd en algorithmes récursifs, mais dans le
cas de Fibonacci et du binôme, ces
algorithmes sont vraiment mauvais (dans
la mesure où le temps d'exécution est
considéré).
Voici les pseudo-code pour ces exemples:
47
 Algorithmes récursifs
Fibonacci
entier f (entier pos. n)
if (n  1) return n
return f (n -1) + f (n -2)

Il s'agit d'un algorithme enO(2n ) car allant

de n à n-1 se multiplie en 2 appels de la
fonction, et chacun de ces appels, à son
tour, se multiplie en 2 autres appels , et
ainsi de suite.
48
dd text Algorithmes récursifs
Coefficients Binomiaux
entier C (entiers n,k)
if (k < 0 | k > n ) return 0
if (k == 0 & n == 0) return 1
return C (n -1,k) + C (n -1,k -1)

Q: Quelle est la complexité?

49
 Algorithmes récursifs
pgcd
entier pgcd (entier positif x, entier positif y)
if (y == 0 ) return x
return pgcd(y, mod(x , y))
Complexité: apparemment, nous n'avons plus le
problème d’une méthode qui explose en
exponentielle comme le binôme ou Fibonacci.
C'est donc un algorithme en O (n) où n est la
plus grande valeur parmi x et y (en supposant
que l’opération mod est O (1))

50
 Algorithmes récursifs
Coefficients Binomiaux
A: Identique à Fibonacci. O(2n ) car allant
de n à n-1 se multiplie en 2 appels de
la fonction
Q: Y at-il un meilleur algorithme?

51
 Algorithmes récursifs
Coefficients Binomiaux
A: Oui! Il suffit de construire le triangle de
Pascal rangée par rangée. c'est O (n 2 ).

52