Définitions et exemple à un seul appel

La récursivité pas à pas

Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Terminaison et validité d’un algorithme

récursif

Thomas Bellitto, Alix Munier-Kordon et Maryse Pelletier

LIP6
Sorbonne Université
Paris

Module LU2IN003 Algorithmique Elémentaire

 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Plan du cours

1 Définitions et exemple à un seul appel

2 La récursivité pas à pas
3 Terminaison et validité d’une fonction récursive
4 Terminaison et validité de la fonction factorielle
5 Recherche d’un élément dans un tableau non trié
6 Calcul de Cnp
7 Conclusion
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Définition
Definition
En mathématiques, une fonction récursive est une fonction qui
est définie à partir d’elle même.
En informatique, une fonction est récursive lorsqu’elle peut
s’appeler elle-même au cours de son exécution.
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Exemple : la fonction factorielle (un seul appel)


1 si n = 0
∀n ∈ N, fact(n) =
n × fact(n − 1) sinon

def f a c t ( x ) :
i f x == 0 :
return 1
else :
r e t u r n x ∗ f a c t ( x−1)
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Notion de Pile

Une Pile P est une structure de données gérée à l’aide des 3

méthodes suivantes :
1 [Link](d)
Place d en sommet de la pile P.
2 [Link]()
Dépile le sommet de la pile P et en renvoie la valeur.
3 [Link]()
Teste si la pile P est vide.
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Contexte d’exécution d’une fonction

Pour pouvoir exécuter une fonction (récursive ou non), le code
d’exécution doit avoir accès aux valeurs des paramètres de la
fonction et des variables locales.
Que devient le contexte d’une fonction qui appelle une nouvelle
fonction ?

def g ( i n t a ) :
i =5
f ( i +2 , 8 )
...

g(3)
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Pile des exécutions

1 A chaque appel de fonction, le contexte d’exécution de la

fonction appelée est empilé au sommet de la pile des
exécutions.
2 Quand on termine l’exécution d’une fonction, son contexte
d’exécution est dépilé de la pile des exécutions.
3 Le sommet de pile contient ainsi le contexte de la fonction
en cours d’exécution.
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Exemple

A l'appel de f(i+2,8) :
f
{ 8
7
second paramètre de f
premier paramètre de f

g { 5
3
i
a

A la fin de f(i+2,8),
retour à g:
g { 5
3
i
a
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Exemple de la factorielle

def f a c t ( n ) :
p r i n t " Appel de f a c t avec n = " , n
i f n==0 :
r e s =1
else :
r e s =n∗ f a c t ( n−1)
p r i n t " R e s u l t a t pour n = " , n , " : " , r e s
return res
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Exemple de la factorielle (suite)

Appel de fact (4)

Appel de f a c t avec n = 4
Appel de f a c t avec n = 3
Appel de f a c t avec n = 2
Appel de f a c t avec n = 1
Appel de f a c t avec n = 0
Resultat pour n = 0 : 1
Resultat pour n = 1 : 1
Resultat pour n = 2 : 2
Resultat pour n = 3 : 6
Resultat pour n = 4 : 24
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Terminaison et validité d’une fonction récursive f (x)

Soit P l’ensemble des valeurs du paramètre x de f

Terminaison Démontrer par récurrence que ∀x ∈ P, f (x) se
termine.
Validité Démontrer par récurrence que ∀x ∈ P, f (x) est
valide.
On peut grouper les deux raisonnements.
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Terminaison et validité de la fonction factorielle

Terminaison Montrer par récurrence sur n que ∀n ≥ 0, fact(n)

se termine.
Validité Montrer par récurrence sur n que ∀n ≥ 0, fact(n)
vaut n!.
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Terminaison et validité de la fonction factorielle

P(k ), k ≥ 0: fact(k) se termine et retourne k !
Par récurrence faible :
Base Pour n = 0, fact(0) retourne 1 = 0!.
Donc P(0) est vérifiée.
Induction Supposons que P(k − 1) soit vérifiée pour une
valeur k ≥ 1 fixée. fact(k) retourne
k ×fact(k-1). Par hypothèse de récurrence,
fact(k-1) se termine et retourne (k − 1)!. Donc,
fact(k) se termine et retourne k × (k − 1)! = k !.
Donc P(k ) est vérifiée.
Conclusion Comme P(0) est vérifiée, et que, pour tout k ∈ N,
P(k ) ⇒ P(k + 1), on en déduit que ∀k ∈ N, P(k )
est vérifiée.
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Recherche d’un élément dans un tableau non trié

def RechercheRec ( elem , tab , n ) :

i f n==0 :
r e t u r n −1
i f t a b [ n−1]==elem :
r e t u r n n−1
r e t u r n RechercheRec ( elem , tab , n−1)

>>> t a b = [ 4 , 8 , 3 , 1 , 9 , 8 , 7 ]
>>> RechercheRec ( 8 , tab , 7 )
5
>>> RechercheRec ( 5 , tab , 7 )
−1
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Terminaison et validité de la fonction RechercheRec

Soit tab un tableau d’entiers de taille supérieure ou égale à n,

et elem un entier.
Terminaison Montrer par récurrence sur n que ∀n ≥ 0,
RechercheRec(elem, tab, n) se termine.
Validité Montrer par récurrence sur n que ∀n ≥ 0,
RechercheRec(elem, tab, n) renvoie
l’indice maximum i ∈ {0, · · · , n − 1} tel que
tab[i] = elem si elem ∈ tab[0 · · · n − 1],
−1 sinon
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Combinaisons

Definition
Une combinaison d’ordre k d’un ensemble E à n éléments est
un sous-ensemble de E ayant k éléments.

Remarque : dans une combinaison, il n’y a pas de répétition et

l’ordre n’a pas d’importance.
Par exemple, dans l’ensemble {1, 2, 3, 4, 5} :
{2, 3, 5} est une combinaison d’ordre 3
{5, 2, 3} est la même combinaison
{5, 2, 5} n’est pas une combinaison.
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Calcul du nombre de combinaisons

Theorem
Soit n ≥ 0 et k ∈ {0, . . . , n}.
Le nombre de combinaisons d’ordre k d’un ensemble E à n
n!
éléments est noté Cnk et vérifie Cnk = k !(n−k )! .

Par exemple il y a 10 combinaisons d’ordre 3 dans l’ensemble

{1, 2, 3, 4, 5}, autrement dit C53 = 10.
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Triangle de Pascal

Theorem (Triangle de Pascal)

k −1
Cnk = Cn−1
k
+ Cn−1 pour 1 ≤ k ≤ n − 1

Ckn k=0 k=1 k=2 k=3 k=4 k=5

n=0 1
n=1 1 1
n=2 1 2 1
n=3 1 3 3 1
n=4 1 4 6 4 1
n=5 1 5 10 10 5 1
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Calcul des Cnk pour n ≥ 0 et k ∈ {0, · · · , n}

def Comb( n , k ) :
i f ( k==n ) or ( k = = 0 ) :
return 1
r e t u r n Comb( n−1,k )+Comb( n−1,k −1)

>>> Comb( 5 , 5 )
1
>>> Comb( 4 , 2 )
6
>>> Comb( 5 , 3 )
10
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Terminaison et validité de la fonction Comb

Terminaison Montrer par récurrence sur n que ∀n ≥ 0,

∀k ∈ {0, · · · , n}, Comb(n,k) se termine.
Validité Montrer par récurrence sur n que ∀n ≥ 0,
∀k ∈ {0, · · · , n}, Comb(n,k) retourne Cnk .
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Exécutions de Comb

def Comb( n , k ) :
p r i n t ( ’ Appel avec n= ’ , n , ’ e t k= ’ , k )
if ( k==n ) or ( k = = 0 ) :
r e s =1
else :
r e s = Comb( n−1,k )+Comb( n−1,k −1)
p r i n t ( ’C( ’ , n , ’,’ , k , ’ )= ’ , r e s )
return res
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Exécutions de Comb(3,2)

>>> Comb( 3 , 2 )
Appel avec n= 3 e t k= 2
Appel avec n= 2 e t k= 2
C( 2 , 2 )= 1
Appel avec n= 2 e t k= 1
Appel avec n= 1 e t k= 1
C( 1 , 1 )= 1
Appel avec n= 1 e t k= 0
C( 1 , 0 )= 1
C( 2 , 1 )= 2
C( 3 , 2 )= 3
3
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Arbre des exécutions de Comb(3,2)

Comb(3,2)
3

Comb(2,2) Comb(2,1)
1 2

Comb(1,1) Comb(1,0)
1 1
 Définitions et exemple à un seul appel
La récursivité pas à pas
Terminaison et validité d’une fonction récursive
Terminaison et validité de la fonction factorielle
Recherche d’un élément dans un tableau non trié
p
Calcul de Cn
Conclusion

Conclusion

1 La terminaison et la validité d’un algorithme récursif se

démontre par récurrence; en général, on démontre ces
deux propriétés ensemble.
2 Le principe de recurrence utilisé peut-être la récurrence
faible ou forte en fonction des appels récursifs.