Editions ENI Livres | Vidéos | e-Formations
Récursivité ou itération ?
Introduction
Le chapitre « Récursivité » a commencé à montrer comment définir un module qui réalise un traitement répété, en utilisant ses propres services. Nous avons aperçu que la réalisation d’un tel module exprime une définition, au sens mathématique du terme, plutôt qu’une suite de transformations à appliquer aux données. Le chapitre « Itération » a étudié, en détail, comment raisonner sur un problème qui transforme les données par un traitement répété. Ce court chapitre réalise une synthèse sur les traitements répétés en comparant les deux méthodes.
La section « Retour sur la récursivité » revient sur le chapitre précédent en présentant plusieurs exemples élémentaires mais significatifs de récursivité simple. La section « Récursivité ou itération ? » donne quelques éléments pour comparer récursivité et itération et met en évidence les raisons pour lesquelles l’itération est préférée à la récursivité pour la programmation de traitements répétés. La section « Exercices »...
Retour sur la récursivité
Un algorithme récursif exprime donc une définition au lieu de dire comment réaliser les transformations sur les données. Revoyons ce point sur un exemple élémentaire, dont l’étude a déjà été commencée au chapitre « Récursivité ».
1. Premier exemple
Rappelons d’abord le problème.
Un caractère est un nombre entier positif ou nul. Dans la suite, un caractère est donc confondu avec son code numérique. Le domaine des valeurs d’un tel entier n’est pas précisé davantage. On peut y penser en supposant, par exemple, que le domaine dépend de la machine utilisée. Le type de données CARACTÈRE permet de définir une variable de type caractère.
L’un de ces caractères est un code particulier. Il est désigné par FIN_CH. Ce caractère n’est jamais un caractère significatif dans une chaîne. Il n’est utilisé que pour marquer la terminaison d’une chaîne. Ainsi, toute donnée de type CHAÎNE contient, comme dernier caractère, celui de code FIN_CH qui en marque la fin. Les caractères d’une chaîne sont numérotés en séquence à partir de 1 pour le premier.
L’accesseur item, défini précédemment, reste disponible dans le répertoire d’instructions. C’est une fonction qui prend en entrée une chaîne de caractères bien formée, c’est-à-dire terminée par FIN_CH, et un entier naturel rang. Elle rend le caractère de la chaîne qui occupe le rang donné, comme dans les chapitres précédents. De même, les fonctions premier et fin définies dans les chapitres précédents restent disponibles. La fonction premier rend une copie du premier caractère de la chaîne qu’elle reçoit en paramètre. La fonction fin retourne une copie de la chaîne qu’elle reçoit en paramètre, mais privée de son premier caractère.
On s’intéresse au calcul du nombre de caractères d’une chaîne. Le caractère FIN_CH n’est pas compté.
Le problème est donc...
Récursivité ou itération ?
Pour comprendre la différence essentielle qui fait préférer un algorithme itératif à un algorithme récursif, étudions le « fonctionnement » des deux versions du calcul de la longueur d’une chaîne de caractères, comme il a été présenté à la section précédente.
Les étapes du calcul récursif sont les suivantes :
(i) : 'abc' ≠ CHAÎNE_VIDE => longueur('abc') = 1 + longueur('bc') ;
(ii) : 'bc' ≠ CHAÎNE_VIDE => longueur('bc') = 1 + longueur('c') ;
(iii): 'c' ≠ CHAÎNE_VIDE => longueur('c') = 1 + longueur('') ;
(iv) : '' = CHAÎNE_VIDE => longueur('') = 0
(j) : longueur('') = 0 => longueur('c') = 1 + 0 = 1 ;
(jj) : longueur('c') = 1 => longueur('bc') = 1 + 1 = 2 ;
(jjj): longueur('bc') = 2 => longueur('abc') = 1 + 2 = 3 Les éléments successifs du calcul, c’est-à-dire les chaînes de caractères sur lesquelles opère l’algorithme, sont placés en attente du résultat intermédiaire pour terminer le calcul. Le calcul de la longueur de ’abc’ est mis en attente du résultat de la longueur de ’bc’. Ce calcul est mis en attente du résultat du calcul de la longueur de ’c’. Ce dernier calcul est mis en attente du résultat du calcul de la longueur de ’’ qui est 0. Alors...
Exercices
|
Exercice résolu 1 : Fonction factorielle |
Transformer l’algorithme de la fonction factorielle étudiée au chapitre « Récursivité » pour en faire un algorithme dont la récursivité est terminale.
Solution
Il suffit d’utiliser un accumulateur initialisé à 1 puisque factorielle(0) =factorielle(1) = 1.
|
Algorithme 3 : Fonction factorielle (récursivité terminale) |
Algorithme factorielle
# n!
Entrée
n : ENTIER
ACC : ENTIER
précondition
n ≥ 0
réalisation
si
n < 2
alors
Résultat
ACC
sinon
Résultatfactorielle(n - 1, ACC x n)
fin si
postcondition
Résultat = n!
fin factorielle La fonction est utilisée ainsi :
k factorielle(10, 1) # calcule 10! avec ACC initialisé à 1 |
Exercice résolu 2 : Fonction appartient |
1. Écrire une fonction appartient qui rend VRAI si et seulement si le caractère qu’elle reçoit en second paramètre compose la chaîne qu’elle reçoit en premier paramètre.
2. La solution proposée est-elle une récursivité terminale ?
Solution
Le résultat est évidemment FAUX lorsque la chaîne de caractères est vide :
ch = CHAÎNE_VIDE => Résultat = FAUX Le résultat est VRAI si le caractère cherché est le premier de la chaîne quand elle n’est pas vide :
ch ≠ CHAÎNE_VIDE => Résultat = (premier(ch) = car) ... Lorsque ce n’est pas le premier, le résultat est VRAI si le caractère appartient au reste de la chaîne :
... ou sinon Résultat = appartient(car, fin(ch))) L’algorithme demandé est donc :
|
Algorithme 4 : Fonction appartient |
Algorithme appartient, infixe
# car appartient-il à ch_?
Entrée
car : CARACTÈRE
ch : CHAÎNE ...Résumé
Ce chapitre est une courte introduction aux problèmes soulevés par la récursivité. Nous avons vu quelques éléments permettant d’être sensibilisé aux inconvénients de la récursivité, mais aussi les avantages incomparables que présentent ces solutions, notamment dans la puissance d’expressivité qu’elles permettent. Nous avons introduit la récursivité terminale et précisé les raisons qui font que ces solutions peuvent être utilisées, en programmation, sans inconvénient majeur avec un compilateur de langage moderne. Il faudrait aussi montrer comment transformer les algorithmes récursifs en algorithmes itératifs et comment prouver un algorithme récursif, mais ces problèmes dépassent le cadre de cette initiation.
