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

Terminaison et validité d’un algorithme

récursif

Alix Munier-Kordon et Maryse Pelletier

LIP6
Sorbonne Université
Paris

Module 2I003 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

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
 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

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

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

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

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

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

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

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

Exemple de la factorielle (suite)

Appel de f a c t ( 4 )

Appel de fact avec n = 4

Appel de fact avec n = 3
Appel de fact avec n = 2
Appel de fact avec n = 1
Appel de fact 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

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

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

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

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

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

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

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

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

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

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

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

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

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