Présentation
Auteur(s)
-
Bernard ROBINET : Professeur des Universités - Directeur scientifique de l’École nationale supérieure des télécommunications
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleINTRODUCTION
Si, dès l’Antiquité, Euclide avait décrit la suite d’opérations permettant de calculer le plus grand commun diviseur de deux entiers, il a fallu attendre le neuvième siècle de notre ère pour qu’un mathématicien arabe, Al Kwarismi (ou Al-Khawarizmi) explicite l’idée de description d’un procédé de calcul par une liste d’actions enchaînées à faire dans l’ordre où elles sont présentées : la notion d’algorithme prend corps, les techniques calculatoires progressent et, franchissant allègrement plusieurs siècles, on arrive à l’époque où l’ordinateur banalise, en quelque sorte, ce type d’artefact qu’est l’algorithme.
En effet, programmer un ordinateur, c’est construire un algorithme dont l’exécution par la machine conduit au résultat recherché ou escompté ; programmer, c’est donc aussi rédiger dans un langage traduisible – par interprétation ou par compilation, peu importe – sur un ordinateur une liste d’actions enchaînées.
Certains différencient avec force les deux activités que sont la création d’algorithmes et leurs rédactions dans des langages de programmation. Pendant longtemps, quelques-uns ont même restreint la programmation à une espèce de travail de codification d’algorithmes dans ces mêmes langages. Ce point de vue n’est pas celui adopté ici : décrire une liste ordonnée d’actions – c’est-à-dire un algorithme – nécessite l’emploi d’un certain langage. Que celui-ci soit le langage mathématique usuel ou toute espèce de sabir ne change rien à l’affaire : il doit être traduit et peut être compris par celui qui l’utilise, que ce soit pour exécution, pour transmission et appropriation. De plus, le langage mathématique usuel pouvant être rendu non ambigu, syntaxiquement et surtout sémantiquement, et, par là, être traduisible sur un ordinateur, on ne voit plus guère de différence avec un langage de programmation.
Aussi, dans la suite, il ne sera pas distingué entre algorithme et programme, et des langages ad hoc seront utilisés pour décrire l’activité de programmation.
L'expertise technique et scientifique de référence
DOI (Digital Object Identifier)
Cet article fait partie de l’offre
Technologies logicielles Architectures des systèmes
(240 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Présentation
Des structures de données aux objets2. Récursivité
Dans un souci de représentation de données chaînées appelées listes, J. McCarthy fonde, dans les années 60, un nouveau langage de programmation, LISP . L’écart entre l’intention de l’auteur et son application s’accroît très vite et le détournement de ce modèle de la programmation s’opère vers une nouvelle façon de concevoir : l’objet que l’on cherche à définir (calculer) est nommément présent dans sa définition (calcul implicite).
-
Ainsi le calcul du plus grand commun diviseur de deux entiers peut être écrit :
PGCD(M,N) = si M ³ N alors
si M = N alors M sinon PGCD(M-N,N) is
sinon PGCD(N,M) is
Cela peut sembler moins une façon de calculer qu’une façon de définir une fonction ; cette pratique, ou ce style, est appelée programmation fonctionnelle.
-
L’exemple suivant est moins trivial :
MIN(A,N) = si N = 1 alors A(1) sinon inf(A(N), MIN(A, N-1)) is
où, en utilisant l’opérateur inf d’arité 2 qui, appliqué à deux valeurs, fournit la plus petite des deux, la définition énonce le fait que si l’on sait calculer le minimum de la sous-suite commençante de longueur N - 1 alors le minimum de la suite de longueur N s’obtient en comparant la valeur précédente à celle du dernier élément.
Une définition récursive en informatique est de même racine qu’une définition implicite en mathématiques : l’affectation et les opérations de base autres que l’alternative en sont exclues, la récursivité est le seul principe de calcul.
2.1 La récursivité simple
On peut cependant se poser la question de savoir s’il existe un lien entre une définition récursive d’un calcul et un algorithme-programme répondant au même problème.
La forte similitude entre définition récursive et définition implicite conduit à développer une espèce de programmation analytique dans laquelle peu d’imagination est nécessaire mais, peut-être, beaucoup de pratique et d’habileté...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Technologies logicielles Architectures des systèmes
(240 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Récursivité
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Technologies logicielles Architectures des systèmes
(240 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
