Cours :

Algorithmique avancée

La récursivité
La récursivité
Une construction est récursive si elle se définit à partir
d'elle-même.

Exemple : le triangle de Sierpinski

 La récursivité
 En informatique, un programme est dit récursif s'il s'appelle
lui même. Il s'agit donc forcément d'une fonction.

Exemple : la factorielle, n! = 1 x 2 x ... x n donc n! = n x (n-1)!

L'appel récursif est traité comme n'importe quel appel de

fonction.
La récursivité
Condition d'arrêt
Puisqu'une fonction récursive s'appelle elle-même, il est impératif
qu'on prévoit une condition d'arrêt à la récursion, sinon le
programme ne s'arrête jamais!

On doit toujours tester en premier la condition d'arrêt, et ensuite, si

la condition n'est pas vérifiée, lancer un appel récursif.
Exemple de la factorielle :
si n ≠ 1, n! = n x (n-1)!, sinon n! = 1.
Condition d'arrêt
Pile d'exécution
La récursivité fonctionne car chaque appel de fonction est différent.

L'appel d'une fonction se fait dans un contexte d'exécution propre,

qui contient :

- l'adresse mémoire de l'instruction qui a appelé la fonction

- les valeurs des paramètres et des variables définies par la
fonction
Exemple : exécution du programme Toto
Pile d'exécution
Pile d'exécution

Prévoir à l'avance le nombre d'appels d'une fonction

récursive pouvant être en cours simultanément en mémoire
est impossible.

La récursivité suppose donc une allocation dynamique de

la mémoire (à l'exécution).

Quand il n'y a pas de récursivité, on peut réserver à la

compilation les zones mémoire nécessaires à chaque appel
de fonction.
Pile d'exécution

Attention : exécuter trop d'appels de fonction fera déborder la pile

d'exécution!
Récursif versus itératif

Rappel : Itérer : répéter n fois un processus en faisant changer la

valeur des variables jusqu’a obtention du résultat.

Un calcul itératif se programme par une boucle (pour ou tant que)

Il est souvent possible d'écrire un même algorithme en itératif

et en récursif.

Exercice:

Donner un algorithme (itératif et récursif)

qui donne la somme 1+2+3+…..+n
Récursif versus itératif

Exemple :

L'exécution d'une version récursive d'un algorithme est

généralement un peu moins rapide que celle de la version itérative,
même si le nombre d'instructions est le même (à cause de la gestion
des appels de fonction).
Récursif versus itératif
Comparaison expérimentale du calcul de la factorielle en itératif et
en récursif.
Récursif versus itératif

Un algorithme récursif mal écrit peut conduire à exécuter bien

plus d'instructions que la version itérative.

Sur des structures de données naturellement récursives, il est bien

plus facile d'écrire des algorithmes récursifs qu'itératifs.

Certains algorithmes sont extrêmement difficiles à écrire en itératif.

La récursivité

 Récursivité simple
Revenons à la fonction puissance x  xn.

Cette fonction peut être définie récursivement :

La récursivité
 Récursivité multiple
Une définition récursive peut contenir plus d’un appel
récursif.

Nous voulons calculer ici les combinaisons Cnp en se servant

de la relation de Pascal :
La récursivité

 Récursivité mutuelle
La récursivité croisée consiste à écrire des fonctions qui
s'appellent l'une l'autre.

Ça peut être le cas pour la définition de la parité :

La récursivité
 Récursivité mutuelle
La récursivité
 Récursivité imbriquée
 La récursivité imbriquée consiste à faire un appel
récursif à l'intérieur d'un autre appel récursif.

La fonction d’Ackermann est définie comme suit :

La récursivité
 Exercice:
Ecrire une fonction qui calcule les valeurs de la
série de Fibonacci, définie par :
u(0) = 0
u(1) = 1
u(n) = u(n−1) + u(n−2)

Ecrivez cette fonction sous forme itérative et sous

forme récursive. Laquelle des deux variantes est
préférable ici ?
La récursivité

La forme récursive est plus facile à écrire et plus proche de la

définition de la fonction, mais elle est moins efficace que la
version itérative
 La récursivité
 Principe et dangers de la récursivité
 Principe et intérêt :
Les mêmes que ceux de la démonstration par récurrence en
mathématiques.
On doit avoir :
– un certain nombre de cas dont la résolution est connue, ces «
cas simples » formeront les cas d’arrêt de la récursion;

– un moyen de se ramener d’un cas « compliqué » à un cas « plus

simple ».
 Récursivité terminale et non terminale

Une fonction récursive est dite terminale si aucun traitement

n'est effectué à la remontée d'un appel récursif (sauf le retour
d'une valeur).

Une fonction récursive est dite non terminale si le résultat de

l'appel récursif est utilisé pour réaliser un traitement (en plus du
retour d'une valeur).

Exemple de non terminalité : forme récursive non terminale de la

factorielle, les calculs se font à la remontée.
Récursivité terminale et non terminale
 Récursivité terminale et non terminale
Exemple de terminalité :

Forme récursive terminale de la factorielle, les

calculs se font à la descente.
 Intérêt de la récursivité terminale

Une fonction récursive terminale est en théorie plus

efficace (mais souvent moins facile à écrire) que son
équivalent non terminale : il n'y a qu'une phase de
descente et pas de phase de remontée.

En récursivité terminale, les appels récursifs n'ont pas

besoin d'êtres empilés dans la pile d'exécution car l'appel
suivant remplace simplement l'appel précédent dans le
contexte d'exécution.
 Intérêt de la récursivité terminale

Certains langages utilisent cette propriété pour exécuter

les récursions terminales aussi efficacement que les
itérations (ce n'est pas le cas de Java).

Il est possible de transformer de façon simple une fonction

récursive terminale en une fonction itérative : c'est la
dérécursivation.
 Dérécursivation

Dérécursiver,
Dérécursiver c’est transformer un algorithme
récursif en un algorithme équivalent ne contenant
pas d’appels récursifs.

Récursivité terminale
Définition :
Un algorithme est dit récursif terminal s’il ne
contient aucun traitement après un appel récursif.
Dérécursivation
Dérécursivation
Exemple : dérécursivation de la factorielle terminale
Dérécursivation
Une fonction récursive non terminale a pour forme générale :

La fonction itérative correspondante doit gérer la sauvegarde des

contextes d'exécution (valeurs des paramètres de la fonction.

La fonction itérative correspondante est donc moins efficace qu'une

fonction écrite directement en itératif.
Dérécursivation
 Remarques
 Les programmes itératifs sont souvent plus efficaces.

 mais les programmes récursifs sont plus faciles à écrire.

 Les compilateurs savent, la plupart du temps, reconnaître les

appels récursifs terminaux, et ceux-ci n’engendrent pas de surcoût
par rapport à la version itérative du même programme.

 Il est toujours possible de dérécursiver un algorithme récursif.

Complexité et récursivité
Exemple : calcul récursif de la factorielle

Paramètre de complexité : la valeur de n

Il n'y a qu'un seul cas d'exécution (pas de cas au pire ou au mieux)
Si n ≠ 1, le calcul de la factorielle de n coûte une comparaison
d'entiers, le calcul de la factorielle de n-1 et une multiplication
d'entiers.
Si n = 1, le calcul de la factorielle coûte une comparaison d'entiers.
Factorielle récursive
On pose une équation de récurrence :
appelons c(n) la complexité
c(n) = ce + c(n-1) + oe si n ≠ 1
c(1) = ce

On résoud cette équation de récurrence :

c(n) = n*ce + (n-1)*oe = O(n)

La complexité de la factorielle récursive est donc linéaire, comme

celle de la factorielle itérative.

A l'exécution, la fonction récursive est un peu moins rapide

(pente de la droite plus forte) du fait des appels récursifs
Complexité et récursivité
En général, dérécursiver un algorithme ne change pas la forme
de sa complexité, pas plus que passer en récursivité terminale!

Il existe diverses techniques pour la résolution des équations de

récurrence (méthode des fonctions génératrices et décomposition
des fractions rationnelles, transformée en Z, …).

Theoreme : soit T(n) une fonction définie par l'e=équation de

récurrence suivante, où b ≥ 2, k ≥ 0, a > 0, c > 0 et d >0 :
T(n) = a*T(n/b) + c*nk
si a > bk alors T(n)=Θ (nlogb(a))
si a = bk alors T(n)=Θ (nk*log(n))
si a < bk alors T(n)=Θ (nk)
 En conclusion
-Les algorithmes récursifs sont simples (c’est simplement une autre
façon de penser).

-Les algorithmes récursifs permettent de résoudre des problèmes

complexes.

-Il existe deux types de récursivités :

-terminale, qui algorithmiquement peuvent être
transformée en algorithme non récursif.
-non terminale
-Les algorithmes récursifs sont le plus souvent plus gourmands en
ressource que leurs équivalents itératifs.
Exercice 1
 Réécrire les algorithmes suivants sous forme
récursive sous forme terminal quand c’est possible.
Solution
Exercice 2

 a – Ecrire un algorithme qui calcule le maximum de

2 nombres réels 
 b – Ecrire un algorithme récursif qui calcule le
maximum de 3 nombres réels en utilisant
l’algorithme du a. Montrer l’arbre d’appels.
 c – Ecrire un algorithme récursif  qui calcule le
maximum de 4 nombres réels en utilisant
l’algorithme du a. Montrer l’arbre d’appels.
 d – L’algorithme est-il récursif ?
Solution
a b

Ici, Maximum2 fait office de condition terminal

de l’algorithme récursif. La pile d’appels est la
suivante :
 c d
  Bien qu’on ait l’impression de
faire une récursion, il s’agit plutôt
d’une surcharge de fonction ou
La pile d’appels est la suivante : d’appel de fonction pour réduire la
taille du problème. Ce n’est pas un
algorithme récursif à proprement
parler.
 Exercice 3
 a – Est-ce que les algorithmes ci-dessous sont des algorithmes
récursifs ? 
 b – Est-ce qu’ils sont terminaux ?
 c – Est-ce qu’ils se terminent ?
 Solution
 a–
 Les algorithmes log et somme sont récursifs : chacun contient au moins un appel à lui même, par
contre, puissance ne l’est pas : il fait appel à l’algorithme puis. Il faut remplacer puis par puissance.
 b – 
 log est terminal, puissance et somme ne le sont pas car ils demandent un calcul lors de la
récursion.
 c–
 log se termine pour tout entier x. L’itération de la division entière par 2 mène à 0, et le cas de base 0
se termine par l’exécution de retourner. 
 Pour l’algorithme puissance (corrigé), le cas de base 0 se termine par l’excéution de retourner. Si
l’algorithme se termine pour la valeur n−1 alors il se termine aussi pour la valeur n est exécutant
retourner. N’oubliez pas qu’un utilisateur peut rentrer n’importe quoi comme puissance(2, – 5) donc
il faut bien vérifier sa terminaison.
 somme ne se termine pas lorsque n est strictement positif. En effet, l’algorithme pour n se termine
seulement si l’algorithme se termine pour n+1. Or, il n’existe pas d’entier strictement positif pour
lesquels l’agorithme s’arrête.
Exercice 4
 Écrivez un programme pour convertir un
nombre décimal en binaire en utilisant la
récursivité.
Solution