Blog ENI : Toute la veille numérique !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Algorithmique
  3. Récursivité
Extrait - Algorithmique Raisonner pour concevoir (3e édition)
Extraits du livre
Algorithmique Raisonner pour concevoir (3e édition) Revenir à la page d'achat du livre

Récursivité

Introduction

Ce chapitre est le second qui introduit la notion de répétition dans les traitements des données après le chapitre « Itération ». Cependant, alors que dans les chapitres précédents, les changements d’états du système s’obtenaient par des instructions qui disaient explicitement les modifications à faire subir aux données, ils s’obtiennent ici en donnant une définition de ces changements. En particulier, les traitements n’utilisent pas l’instruction d’affectation, sauf marginalement, pour donner une valeur à la pseudo-variable Résultat afin de préciser ce que calcule et retourne une fonction.

La deuxième section introduit la récursivité dans les traitements sur les chaînes de caractères. On montre ce qu’est une définition récursive et on applique ce type de définition à la spécification d’algorithmes sur les chaînes de caractères. La section suivante donne quelques exemples de spécifications ou de traitements récursifs sur les nombres. La quatrième section, pour finir, commence l’étude d’un problème que l’on rencontre souvent : l’édition d’un nombre. Il s’agit de transformer un nombre donné pour obtenir les caractères...

Introduction à la récursivité : les chaînes de caractères

La récursivité est introduite dans cette section comme une méthode générale de spécification algorithmique des algorithmes. Cette phrase est déjà, en soi, une phrase qui énonce une propriété récursive : la spécification d’un algorithme est un algorithme.

La première partie présente la récursivité sur un exemple simple : la définition d’un mot du langage. La deuxième partie étudie des exemples de spécifications récursives d’algorithmes de traitement sur les chaînes de caractères. La troisième partie donne la solution complète de quelques exercices instructifs et la dernière, enfin, propose de résoudre divers exercices dont la solution n’est pas développée ici.

1. Présentation de la récursivité

Considérons un mot. Un mot est une chaîne de caractères de longueur finie. Pour simplifier cet exposé, on se restreint aux mots, de la langue ou pas, écrits en minuscules et sans caractère accentué : ’maison’, ’poisson’, ’voiture’ sont des exemples de mots qui nous intéressent. ’École’, ’Maison’, ’élection’ sont exclus, du fait des caractères accentués ou des majuscules qu’ils contiennent.

Comment donner une définition formelle d’un mot ?

Il s’agit de donner une définition qui s’applique à un mot quelconque, sans accent ni capitale, comme on l’a dit. Il est possible d’en donner la définition suivante :

Définition 1

Un mot est soit un caractère, soit un caractère suivi d’un mot.

Autrement dit, un mot, choisi parmi ceux auxquels on se restreint, est soit une chaîne de caractères réduite à un seul caractère ou sinon, une chaîne de caractères constituée d’un premier caractère suivi d’un autre mot. Ainsi, par exemple, le mot ’maison’ est constitué du caractère ’m’ suivi du mot ’aison’. Le mot ’aison’ est formé de ’a’ suivi du mot ’ison’......

Les nombres et la récursivité

Les nombres fournissent de nombreux exemples simples de récursivité. En fait, les définitions mathématiques sont souvent récursives. Cette section vous propose quelques exercices sur ce sujet. Ceux qui ne peuvent se réconcilier avec les Mathématiques peuvent passer à la section suivante.

1. Arithmétique

Soit images/ic07.png l’ensemble des entiers : images/ic07.png = { ..., -2, -1, 0, 1, 2, ...}. On suppose que les seules opérations actuellement définies sur images/ic07.png sont successeur, qui rend le successeur d’un entier dans la liste ordonnée de ses éléments et prédécesseur la fonction duale de la précédente.

Exercice 6 : Arithmétique sur les entiers

1. Écrire l’algorithme de l’addition de deux entiers.

2. Écrire l’algorithme qui rend l’opposé d’un entier.

La différence de deux entiers est la somme du premier avec l’opposé du deuxième.

3. Écrire l’algorithme qui calcule la différence de deux entiers.

Le produit de deux entiers se calcule en effectuant une addition répétée. Ainsi, par exemple, 7 x 5 est la somme de 5 termes égaux à 7.

4. Écrire les algorithmes de la multiplication et de la division.

Une solution est donnée à cet exercice dans les éléments disponibles en téléchargement...

Nombres et chaînes de caractères : édition d’un entier

On rencontre souvent le problème de l’édition d’un entier dans différents contextes. Cette section aborde ce problème que nous aurons l’occasion de retrouver dans les chapitres ultérieurs et notamment au chapitre « Édition d’un nombre » où son étude sera développée.

En Français, le mot chiffre est utilisé avec plusieurs sens. Il désigne souvent un nombre entier inférieur strictement à la base de numération, par exemple, un nombre entier compris entre 0 et 9 en base dix. Il désigne aussi le caractère représentant l’un de ces nombres, par exemple le caractère ’7’ représentant le nombre 7. Il possède encore bien d’autres sens ; un dictionnaire permet de se rendre compte de la richesse polysémique de ce mot.

Restons en base dix pour simplifier. Nous devons distinguer soigneusement un nombre inférieur strictement à dix du caractère qui représente ce nombre. Il nous faut donc faire une différence bien marquée entre l’objet mathématique, le nombre, qui est indépendant de sa représentation, et le chiffre qui le représente dans un système de codage particulier. Ainsi, le nombre de jours de la semaine est représenté par la chaîne de caractères ’sept’, par le chiffre ’7’, par la suite de chiffres, c’est-à-dire la chaîne de caractères, ’111’ en base deux, etc. Ce que nous devons intégrer, c’est...

Problèmes

Cette section pose quelques problèmes plus difficiles. Ils nécessitent de la réflexion et un peu d’invention pour être résolus d’une façon qui soit praticable ensuite pour être programmée.

1. Recherche par dichotomie dans un tableau trié

Le chapitre « Itération » a résolu le problème en définissant une fonction itérative.

Exercice résolu 5 : Recherche récursive par dichotomie dans un tableau trié

On demande de résoudre le même problème en définissant une fonction récursive.

Une solution est étudiée dans les éléments disponibles en téléchargement depuis la page Informations générales.

2. Palindromes

On appelle palindrome un texte qui est le même que son image miroir. Ainsi, par exemple, les mots ’LAVAL’, ’non’, ’26762’ sont des palindromes. Autrement dit, un palindrome se lit de droite à gauche comme de gauche à droite.

Avec cette définition, ’Laval’ ou ’non !’ ne sont plus des palindromes. Pour le premier, la majuscule initiale et pour le second l’espace et le point d’exclamation viennent perturber l’image miroir du mot. De même, la phrase ’Élu par cette crapule’ serait un palindrome si la majuscule accentuée au début de la phrase était la lettre ’e’ et si les espaces étaient supprimées.

Existe-t-il des phrases palindromes ? Le problème est compliqué par les caractères séparateurs, comme l’espace, les signes de ponctuation… De plus, une phrase bien formée se termine toujours par un point, mais son premier caractère n’est...

Résumé

Ce chapitre a introduit la notion de traitements répétés. On élabore une définition des changements des états du logiciel au lieu de dire explicitement les transformations à faire subir aux données. On peut ainsi définir les algorithmes en énonçant des clauses sans effet de bord pour préciser les précondition, postcondition et invariant de leur spécification. Les chapitres suivants utiliseront intensivement la récursivité. C’est certainement une notion difficile à aborder pour une initiation. Il est tout à fait possible de s’en passer et d’exprimer les spécifications en utilisant des formules empruntées aux Mathématiques ou à la langue française. Il faut alors veiller à rester rigoureux.