Chapitre 1 Récursivité Algo-STD

ChapJtrF 1
Récursivité
CaractÏristiques principales
• Une procédure (ou fonction) récursive comporte au moins un appel à elle-
même, alors qu’une procédure (ou fonction) non récursive ne peut com-
porter que des appels à d’autres procédures (ou fonctions).
• La récursivité permet d’écrire des programmes (algorithmes) plus facile-
ment, et de manière élégante.
• Les programmes (algorithmes) itératifs sont souvent plus efficaces que les
programmes (algorithmes) récursifs.
• Une procédure récursive n’est jamais plus rapide que son homologue itérative.
DÏDoupage de la rÏcursivitÏ

Pour décrire un algorithme récursif,il convient d’analyser le problème afin :
• d’identifier le cas particulier ;

• d’identifier le cas général qui permet d’effectuer la récursion.
SchÏma gÏnÏral
Algorithme Recur (Paramètres) ;

Si (Test-arrêt) Alors
Instruction du point d’arrêt
Sinon
Instructions ;
Recur (Paramètres changés);
Instructions
Fin Si
Exemple
Fonction ADD (N : entier) : entier;

Si (N >1) Alors
ADD ←N + ADD(N −1)
Sinon
ADD ←1
Fin Si
Pour simplifier, on peut adopter la notation du langage C dans l’écriture des

algorithmes. Par exemple, la fonction ADD peut être réécrite comme suit :
Fonction ADD (N : entier) : entier;

Si (N >1) Alors
retourner (N + ADD(N −1))
Sinon
retourner (1)
Fin Si
RÏcursivitÏ terminale
Un algorithme est récursif terminal s’il ne contient aucun traitement après un
appel récursif.
Schéma Général Légende

Algo P(u) u est la liste des paramètres
Si C(u) C(u) est la condition sur les paramètres u
Alors
B(u); B(u) est le traitement de base de Algo P(u)
P(a(u)) P(a(u)) est l’appel récursif avec des paramètres u transformés
Sinon
T(u) T(u) est le traitement de terminaison (arrêt de l’algorithme)
Finsi
Remarque
Il est toujours possible de dérécursifier un algorithme récursif.
• S’il est récursif non-terminal, on utilise les piles pour sauvegarder le con-
texte.
• S’il est récursif terminal, il est inutile d’utiliser les piles ; l’algorithme se
transforme alors comme suit
Schéma général de l’algorithme P transformé en l’algorithme P’DJBQSÒT
Algo P’(u);
Tant que (C(u)) faire
B(u);
u ← a(u)
Fait
T(u)
ExemplesdefonctionsrÏcursivesnon-terminales
• La fonction ADD présentée précédemment en 1.4 est récursive non-terminale.
• La fonction suivante qui fait l’addition de deux entiers est également

récursive non-terminale.
Fonction PLUS (a,b : entier) : entier;

Si (b=0) Alors
retourner (a)
Sinon
retourner (1 + PLUS (a,b−1))
Fin Si
L’exécutiondelafonctionPLUS(4,2)estmontréedansletableausuivant:
Appel Exécution Valeur retournée

PLUS(4,2) 1+PLUS(4,1)1 -
PLUS(4,1) +PLUS(4,0) -
PLUS(4,0) PLUS ←4 4 est le résultat au 1er retour
1 + 4 : 5 est le résultat au 2eme retour
1 + 5 : 6 est le résultat au dernier retour
correspondant à l’appel PLUS(4,2)
• Enfin, la fonction Somme cubic suivante qui calcule la somme cubique des
N premiers entiers est également une fonction récursive non-terminale.
Fonction Somme cubic( N : entier) : entier;
Si (N = 0) Alors
retourner (0)
Sinon
retourner (Somme cubic (N − 1)+ N 3 )
Fin Si
L’exécution de la fonction Somme cubic (3) est répertoriée dans le tableau ci-
après :
Appel Exécution Valeur retournée
Somme cubic (3) Somme cubic (2) + 33 -
Somme cubic (0) Somme cubic ← 0 0 est le résultat au 1er retour
9 + 33 : 36 est le résultat au dernier retour
qui est la valeur correspondant
à l’appel Somme cubic (3)
ExemplesdefonctionsrÏcursivesterminales
• La fonction qui calcule le PGCD de manière récursive est une fonction

récursive terminale. Un pseudo code de cette fonction est le suivant :
FonctionPGCD(A,B:entier):entier;
Si (A6=B) Alors
Si (A > B) Alors
retourner PGCD (A − B, B)
Sinon
reourner PGCD (A, B − A)
Fin Si
Sinon
retourner (A)
Fin Si
Cette fonction est récursive terminale; le pseudo code de la fonction itérative

équivalente est donné par la fonction PGCD1 suivante :
FonctionPGCD1(A,B:entier):entier;
Tant que (A6=B) faire
Si (A > B) Alors
A←A−B
Sinon
B ←B−A
Fin Si
Fait
PGCD1 ← A
• Unautreexempledefonctionrécursiveterminaleestlafonctionrécursive
booléenne (prédicat) qui indique si un nombre entier naturel est pair ou
non (impair). Elle consiste en le pseudo code suivant :
Fonction Parité (N : entier) : booléen ;

Si (N =0) Alors
retourner (vrai)
Sinon
Si (N = 1) Alors
retourner (faux)
Sinon
retourner Parité(N − 2)
Fin Si
Fin Si
Ce code estéquivalent au code suivant :

Si (N >1) Alors
retourner Parité(N − 2)
Sinon
Si (N = 0) Alors
retourner (vrai)
Sinon
retourner (faux)
Fin Si
Fin Si
ce dernier, produit le code itératif suivant :

Tant que (N >1) faire
N ←N −2
Fait
Si (N = 0) Alors
Parité ← vrai
Sinon
Parité ← faux
Fin Si

Chapitre 1 Récursivité Algo-STD

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre 1 Récursivité Algo-STD

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Chapitre 1 Récursivité Algo-STD

Transféré par

Droits d'auteur :

Formats disponibles

ChapJtrF 1

DÏDoupage de la rÏcursivitÏ

• d’identifier le cas particulier ;

Algorithme Recur (Paramètres) ;

Fonction ADD (N : entier) : entier;

Pour simplifier, on peut adopter la notation du langage C dans l’écriture des

Fonction ADD (N : entier) : entier;

Schéma Général Légende

Schéma général de l’algorithme P transformé en l’algorithme P’DJBQSÒT

• La fonction suivante qui fait l’addition de deux entiers est également

Fonction PLUS (a,b : entier) : entier;

Appel Exécution Valeur retournée

• La fonction qui calcule le PGCD de manière récursive est une fonction

Cette fonction est récursive terminale; le pseudo code de la fonction itérative

Fonction Parité (N : entier) : booléen ;

Ce code estéquivalent au code suivant :

Fonction Parité (N : entier) : booléen ;

ce dernier, produit le code itératif suivant :

Vous aimerez peut-être aussi

Chapitre 1 Récursivité Algo-STD

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre 1 Récursivité Algo-STD

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Chapitre 1 Récursivité Algo-STD

Transféré par

Droits d'auteur :

Formats disponibles

ChapJtrF 1

 DÏDoupage de la rÏcursivitÏ

• d’identifier le cas particulier ;

Algorithme Recur (Paramètres) ;

Fonction ADD (N : entier) : entier;

Pour simplifier, on peut adopter la notation du langage C dans l’écriture des

Fonction ADD (N : entier) : entier;

Schéma Général Légende

Schéma général de l’algorithme P transformé en l’algorithme P’DJBQSÒT

• La fonction suivante qui fait l’addition de deux entiers est également

Fonction PLUS (a,b : entier) : entier;

Appel Exécution Valeur retournée

• La fonction qui calcule le PGCD de manière récursive est une fonction

Cette fonction est récursive terminale; le pseudo code de la fonction itérative

Fonction Parité (N : entier) : booléen ;

Ce code estéquivalent au code suivant :

Fonction Parité (N : entier) : booléen ;

ce dernier, produit le code itératif suivant :

Vous aimerez peut-être aussi

DÏDoupage de la rÏcursivitÏ

Schéma général de l’algorithme P transformé en l’algorithme P’DJBQSÒT