:: wikimiki.org ::
| Algorithme Récursif |
Algorithme récursif
Un algorithme récursif est un algorithme dans lequel une fonction s'appelle elle-même. Pour éviter une exécution infinie, une condition d'arrêt permet d'arrêter l'algorithme. En d'autres termes, la fonction continue de s'appeler tant que la condition d'arrêt n'est pas vérifiée.
Exemple de calcul de la factorielle d'un entier (supérieur à 0) par une fonction récursive :
factorielle(entier k):entier
si k=0
alors renvoyer 1
sinon renvoyer k
- factorielle(k-1)
fsi
Dans cet exemple, on continue d'appeler factorielle tant que k est différent (c'est-à-dire supérieur, pour un entier naturel) à 1. C'est la condition d'arrêt..
- En Visual Basic cela donne la fonction suivante ( utilisable dans Excel ) :
Private Function Factorielle(By Val Nombre) As Long
Résultat = 1 ' pour l'initialisation
Do
Résultat= Résultat+ Nombre
Nombre= Nombre - 1
Loop While Nombre> 0
Factorielle= Résultat
End Function
Cet exemple est légérement différent de celui-ci dessus dans la mesure ou l'on initialise d'abord à 1 et ou la borne de la boucle d sortie est égale à zéro .
Voir aussi
- Récursion terminale
- Récursivité
Catégorie:Algorithmique
Algorithme ko:알고리즘 ja:アルゴリズム th:อัลกอริทึม
Catégorie:Algorithmique
On nomme algorithmique la science des algorithmes, visant à étudier les opérations nécessaires à la réalisation d'un calcul. On parle également de procédé ou de procédure. Une recette de cuisine constitue par exemple un algorithme parfaitement défini.
Historique
Antiquité
Les algorithmes dont on a retrouvé des descriptions exhaustives ont été utilisés dès l'époque des Babyloniens, pour des calculs concernant le commerce et les impôts.
L'algorithme le plus célèbre est celui attribué à Euclide permettant de trouver le plus grand commun diviseur de deux nombres.
Etude systématique
L'algorithmique a été systématisée par le mathématicien persan Al Kwarizmi (780-850), auteur d'un ouvrage décrivant des méthodes de calculs algébriques (ainsi que d'un autre introduisant le zéro des Indiens). Son nom donna au moyen-âge le nom "algorisme" qui devint algorithme avec lady Ada Lovelace, fille de lord Byron et assistante de Charles Babbage (1792-1871).
On peut voir une allusion à la méthode algorithmique chez René Descartes dans le Discours de la méthode : « diviser chacune des difficultés que j'examinerois, en autant de parcelles qu'il se pourroit, et qu'il seroit requis pour les mieux résoudre. » Néanmoins, cette approche ne parle ni de boucles, ni d'itérations.
Le substantif algorithmique désigne la méthode utilisant des algorithmes. Le terme est également employé comme adjectif.
Un algorithme énonce une résolution sous la forme d'une série d'opérations à effectuer. La mise en œuvre de l'algorithme consiste en l'écriture de ces opérations dans un langage de programmation et constitue alors la brique de base d'un programme informatique.
Les informaticiens utilisent fréquemment l'anglicisme implémentation pour désigner cette mise en œuvre. L'écriture en langage informatique est aussi fréquemment désignée par le terme « codage », qui n'a ici aucun rapport avec la cryptographie, mais qui se réfère au terme « code source » pour désigner le texte, en langage de programmation, constituant le programme. L'algorithme devra être plus ou moins détaillé selon le niveau d'abstraction du langage utilisé ; autrement dit, une recette de cuisine doit être plus ou moins détaillée en fonction de l'expérience du cuisinier.
Exemples d'algorithme
Il existe un certain nombres d'algorithmes classiques, utilisés pour résoudre des problèmes ou plus simplement pour illustrer des méthodes de programmation. On se réfèrera aux articles suivants pour de plus amples détails :
- Tours de Hanoï, problème célèbre illustrant la programmation récursive.
- Problème du tri, ou comment trier un ensemble de nombres le plus rapidement possible.
- Problème des huit dames, placer huit dames sur un échiquier sans qu'elles puissent se prendre entre elles.
La principale notion mathématique dans le calcul du coût d'un algorithme précis sont les notions de négligeabilité (notée o(f(n)), « petit o ») et de domination (notée O(f(n)), « grand o »), où f est une fonction mathématique de n, variable désignant la quantité d'informations (en bits, en nombre d'enregistrements…) manipulée dans l'algorithme. Les fonctions mathématiques relèvent de l'analyse. En algorithmique on trouve souvent des complexités du type :
- indépendant de la taille de la donnée
- , complexité logarithmique
- , complexité linéaire
- , complexité quasi-linéaire
- , complexité quadratique
- , complexité cubique
- , complexité polynômiale
- , complexité quasi-polynômiale
- , complexité exponentielle
- , complexité factorielle
Sans entrer dans les détails mathématiques, on peut dire que lorsque l'on calcule l'efficacité d'un algorithme (sa complexité algorithmique), on cherche davantage à connaître l'évolution du nombre d'instructions de base en fonction de la quantité de données à traiter (par exemple, dans un
algorithme de tri, le nombre de lignes à trier), que le coût exact en secondes et en quantité de mémoire. Baser le calcul de la complexité d'un algorithme sur le temps qu'un ordinateur particulier prend pour effectuer le-dit algorithme ne permet pas de prendre en compte la structure interne de l'algorithme ni la particularité de l'ordinateur : selon sa charge de travail, la vitesse de son processeur, la vitesse d'accès aux données ou même l'exécution de l'algorithme (qui peut faire intervenir le hasard) le temps d'exécution ne sera pas le même.
Quelques indications sur l'efficacité des algorithmes
Souvent, l'efficacité d'un algorithme n'est connue que de manière asymptotique, c'est-à-dire pour de grandes valeurs du paramètre n.
Lorsque ce paramètre est suffisamment petit, un algorithme de complexité supérieure peut en pratique être plus efficace.
Ainsi, pour trier un tableau de 30 lignes (c'est un paramètre de petite taille), il est inutile d'utiliser un algorithme évolué comme
Quicksort (l'un des algorithmes de tri les plus efficaces en moyenne) : l'algorithme de tri le plus trivial sera suffisamment efficace.
À noter aussi : entre deux algorithmes dont la complexité est identique, on cherchera à utiliser celui dont l'occupation mémoire est la plus faible. L'analyse de la complexité algorithmique peut également servir à évaluer l'occupation mémoire d'un algorithme. Enfin, le choix d'un algorithme plutôt qu'un autre doit se faire en fonction des données que l'on s'attend à lui fournir en entrée. Ainsi, le Quicksort (ou tri rapide), lorsque l'on choisit le premier élément comme pivot, se comporte de façon désastreuse si on l'applique à une liste de valeur ... déjà triée ! Il n'est donc pas judicieux de l'utiliser si on prévoit que le programme recevra en entrée des listes à peu près triées.
Un autre paramètre à prendre en compte est la localité de l'algorithme. Par exemple pour un système à mémoire virtuelle qui dispose de peu de mémoire (par rapport au nombre de données à traiter), le Tri rapide sera normalement plus efficace que le Tri par tas car le premier ne passe qu'une seule fois sur chaque élément de la mémoire tandis que le second accède à la mémoire de manière discontinue (ce qui augmente le risque de "swapping").
Les heuristiques
Pour certains problèmes, les algorithmes ont une complexité beaucoup trop grande pour obtenir un résultat en temps raisonnable, même si l'on pouvait utiliser une puissance de calcul phénoménale. On est donc amené à rechercher une solution la plus proche possible d'une solution optimale en procédant par essais successifs. Puisque toutes les combinaisons ne peuvent être essayées, certains choix stratégiques doivent être faits. Ces choix, généralement très dépendants du problème traité, constituent ce qu'on appelle une heuristique. Le but d'une heuristique est donc de ne pas essayer toutes les combinaisons possibles avant de trouver celle qui répond au problème, afin de trouver une solution approchée convenable (qui peut être exacte dans certains cas) dans un temps raisonnable.
C'est ainsi que les programmes de jeu d'échecs, de jeu de go (pour ne citer que ceux-là) font appel de manière très fréquente à des heuristiques qui modélisent l'expérience d'un joueur. Certains logiciels antivirus se basent également sur des heuristiques pour reconnaître des virus non répertoriés dans leur base, en s'appuyant sur des ressemblances avec des virus connus.
Applications
- Cryptologie et Compression de données
- Structure de données, Algorithmes de tri et Recherche dichotomique
- Allocation de mémoire et ramasse-miettes
- Informatique musicale
- Algorithme génétique en informatique décisionnelle
Voir aussi
- Al-Khuwarizmi
- Algorithme récursif
- Algorithme réparti
- Langage K
- Métaheuristique
- Structure de contrôle
Liens externes
- [http://www-ipst.u-strasbg.fr/pat/program/algo.htm Introduction à l'algorithmique, avec des exemples en langage C]
- [http://www.pise.info/algo/codage.htm Initiation à l'algorithmique]
- [http://www.myalgorithm.com Algorithmes de base dans plusieurs langages de programmation]
Fonction (informatique) ja:関数 (プログラミング)
En informatique, une fonction est un ensemble d'instructions réalisant une certaine tâche.
Une fonction prend zéro ou plusieurs paramètres et renvoie éventuellement un résultat. Une fonction qui modifie ses paramètres est appelée procédure. Une fonction propre à un objet est plutôt désignée par le terme de méthode.
Les fonctions réalisant des tâches similaires et dont l'objectif est d'être réutilisées par plusieurs programmes sont regroupées dans des bibliothèques.
Un paradigme de programmation dans lequel toute l'application est vue comme un ensemble de fonctions qui s'enchaînent et s'appellent mutuellement est dit fonctionnel.
Une fonction en informatique se distingue principalement de la fonction mathématique par le fait qu'en plus de calculer un résultat à partir de paramètres, la fonction informatique peut avoir des effets de bord : par exemple afficher un message à l'écran, jouer un son, ou bien piloter une imprimante.
Catégorie:Programmation informatique
Entier naturelEn mathématiques, un entier naturel (aussi appelé nombre naturel) est un nombre entier et positif, comme 0, 1, 2, 3, 4, 5... 12, 512, ...
Il s'agit donc de nombres qui permettent de compter les objets quand ils sont en quantité discrète ; par exemple, les doigts, les feuilles d'un arbre. Ils ne permettent pas de mesurer des quantités continues comme une longueur, un volume ou une masse.
Certains mathématiciens ne comptent pas zéro comme un entier naturel.
Bien que cette notion paraisse intuitive, leur définition formelle en mathématiques n'a pas été simple à concrétiser. Les axiomes de Peano définissent l'ensemble des entiers naturels, noté N ou . On note l'ensemble des entiers naturels privé de l'élément zéro.
Les entiers naturels, une abstraction des objets réels
Au départ sont les objets, les animaux. On a des fruits, un troupeau ... Ces objets n'ont rien à voir entre eux, mais ils ont pourtant une caractéristique commune : dans un panier, les tomates sont distinctes et à peu près identiques, dans un troupeau, les vaches sont elles aussi distinctes et à peu près identiques.
On a donc inventé des objets qui n'existent que dans l'esprit et qui ont la propriété suivante : ils sont distincts et interchangeables. Ce sont des objets sans aucun support matériel, de purs concepts. On écrira donc « un (1) », « deux (2) », « trois (3) » ... Trois quoi ? Trois de ces objets inventés et sans support matériel, trois « unités ». On écrira V le nombre de vaches et T le nombre de tomates par exemple, ces deux variables sont manipulables mathématiquement, indépendamment des objets qu'elles représentent.
On a donc extrait une propriété qui nous intéressait (la « dénombrabilité »), et on a fabriqué un objet imaginaire qui n'avait que cette propriété ; cet objet est l'« unité ».
Ce processus mental est connu sous le nom d'abstraction, on fait abstraction de la qualité de l'objet pour s'intéresser uniquement à la quantité.
Comme une quantité ne peut être moindre que un, zéro n'est pas un nombre ! heureusement d'ailleurs, sinon, 1 serait le deuxième nombre !
Quelques pistes à propos du zéro
Les chiffres vont de 1 à 9 et permettent d’écrire les nombres. Qu’en est-il du zéro ? Zéro est-il un chiffre ?
Zéro, çifr en arabe, signifie vide. C'est la racine du mot chiffre, elle maintient une vérité fondamentale, l'illusion de tout ce qui est quantifiable. Le zéro métaphysique est le « Non-être » symbolisé par le « vide » dans les traditions orientales.
« Avant l'Un, que peux-tu compter ? » demande l'auteur du Sepher Ietsirah. Peut-il y avoir une quantité moindre que zéro ?
« Avancer qu'une quantité négative isolée est moindre que zéro, c'est couvrir la science des mathématiques, qui doit être celle de l'évidence, d'un nuage impénétrable, et s'engager dans un labyrinthe de paradoxes tous plus bizarres les uns que les autres. » (Carnot - Notes sur les quantités négatives)
En effet, zéro « représente purement et simplement l'absence de toute quantité, car une quantité qui serait moindre que rien est proprement inconcevable. » (René Guénon, Les Principes du Calcul infinitésimal – NRF Gallimard, 1946, p. 97) Force est de constater qu'en mathématique la division par zéro n'a pas de sens ; elle est dite impossible A noter que le concept de nombre nul ainsi que la définition de l'infini comme inverse du zéro apparaissent dans la publication du mathématicien et astronome indien Brahmagupta (628). (Voir Georges Ifrah, Histoire universelle des chiffres, R. Laffont, 1994, tome II, p. 460).
Leibniz, redécouvrant la nature binaire de la manifestation, remplace le 1 et le 2 par le 0 et le 1 qui sont restés les deux signes utilisés dans le langage des ordinateurs. « Dans son arithmétique binaire, Leibniz voulait voir l'image de la Création. Il imaginait que l'unité représentait Dieu et zéro le néant ; que l'Etre Suprême avait tiré tous les êtres du néant ; de même que l'unité et le zéro expriment tous les nombres dans son système de numération. » (Laplace - Exposition du Système du Monde - Livre V, chap. VI) Ce point de vue amène cette remarque de René Guénon : « Les mathématiciens ayant (...) le tort de regarder le zéro comme une sorte de symbole du néant, comme si le néant pouvait être symbolisé par quoi que ce soit, il semble résulter de là que l'équilibre est l'état de non-existence, ce qui est une conséquence assez singulière » (Les Principes du Calcul infinitésimal - Op. cit., p. 106).
Les mathématiques n'ont pas cessé pourtant d’abandonner toute base métaphysique. Pascal serait très étonné de nos soi-disant certitudes. Pour lui, il était évident que zéro représentait le rien. N'a-t-il pas écrit : « J'en sais qui ne peuvent comprendre que qui de zéro ôte quatre reste zéro » ? (Pensées - Hachette, 1973, p. 30) Depuis, le résultat de cette opération est devenu (-4). Les nombres négatifs sont bien une « création » de l'homme au sens où l'entend Guénon.
Qu'en est-il actuellement ? Un mathématicien contemporain écrit, à la page zéro de son livre : « Dans le langage courant, zéro désigne aussi bien un nombre - le plus petit possible dans un comptage - que le chiffre qui le représente. Introduit initialement comme signe dans la numération de position, son statut de nombre ne fut reconnu que beaucoup plus tard. » (François Le Lionnais, Les nombres remarquables - Paris : Herman, 1983, p. 0). Voilà donc un livre dont la première page est la page 0, la deuxième la page 1...
L'absence de quantité peut-elle faire nombre ? La logique purement mentale a fini par supplanter l'intelligence métaphysique.
Avant l'invention du zéro par les Indiens, on laissait en effet, dans l'écriture d'un nombre, un espace pour indiquer l'absence de quantité. Cela était cause de maintes erreurs : « Des tablettes portant des inscriptions cunéiformes prouvent qu'à cette époque, sous le signe du roi Hammourabi, les mathématiciens de Babylone réalisaient d'étonnantes prouesses de calcul. L'usage du zéro leur était inconnu et un espace symbolisait l'absence de chiffre d'un ordre donné ; cependant, cet espace était souvent oublié, d'où une certaine ambiguïté dans les nombres transcrits. » (Bergmani, Les Mathématiques - Life, 1965, p 16).
Al-Khowarizmi écrit : « Nous avons décidé d'exposer la manière de compter des Indiens, à l'aide de IX caractères et de montrer comment, grâce à leur simplicité et leur concision, ces caractères peuvent exprimer tous les nombres. » (Livre de l'addition et de la soustraction d'après le calcul des Indiens) Dans son traité sur les nombres hindous, il a popularisé une sentence qui devint traditionnelle : « Lorsqu'il ne reste rien, faites figurer un petit cercle pour que la place ne demeure pas vide. » L'emploi des dix signes de notre numération est cependant antérieur.
Cependant, la numération décimale basée sur le principe de position et sur l'emploi du signe “zéro” était déjà utilisée par le chimiste Abu Musa Gabir ibn Hayyan, qui vivait vers 776, dans son livre Les Poissons. (Voir Georges Ifrah,- Histoire universelle des chiffres , op. cit).
Dès le début du VIe siècle les mathématiciens indiens Brahmagupta et Bhâskara révélaient dans leurs œuvres une parfaite maîtrise de la numération décimale de position au moyen de neuf chiffres et du zéro dont la découverte remonterait aux IVe-Ve siècles. En Europe, c'est le moine Gerbert, devenu pape sous le nom de Sylvestre II, qui introduisit le zéro dans la numération au Xe siècle.
On a peine à imaginer ce que fut l'apport des chiffres indiens. En arabe ancien, comme en hébreu et en grec, on ne distinguait pas les chiffres des lettres et ceux-ci étaient à l'origine des hiéroglyphes. (Voir A. Youschkevitch, Les Mathématiques arabes : XIIe-XIVe s., Paris : A. Vrin, 1976, tome I, p. 165). Ainsi le radical hébreu yd se retrouve aussi bien dans y(o)d, dixième lettre de l'alphabet signifiant « dix », que dans y(a)d signifant « main ».
L'emploi du zéro était connu des Mayas qui le représentait par la coquille, liée à la mort, ou par l'escargot. (Voir Girard Raphaël, Le Polpol-Vuh : histoire culturelle des Mayas-Quichés - Paris, 1954, p. 42).
Zéro, chez les Babyloniens, « ne fut jamais conçu comme un nombre : synonyme de “vide” seulement, il ne correspondit jamais au sens de la “quantité nulle”. » (Georges Ifrah, Op. cit., tome I, p. 774). Comme les Babyloniens, les Egyptiens laissaient un espace vide pour mettre en évidence le fait qu'il n'y avait rien. Ceci est symboliquement plus juste, mais beaucoup moins pratique et source de multiples erreurs.
Comment représenter le rien par un signe ? La représentation par un petit rond, un cercle, est incorrecte puisque le cercle est engendré à partir du zéro. La ligne droite, courbe ou circulaire, que l'on dit formée de points n'est-elle pas en réalité formée de zéros puisque le point n’a ni longueur, ni largeur, ni épaisseur et n’est donc représentable que par approximation ?
Paradoxalement, le vide est plein : chacun sait que « la Nature a horreur du vide ». Au plan métaphysique, la mort à soi-même est vacuité. « Qui atteint à sa vertu primitive s'identifie avec l'origine de l'Univers et par là avec le vide. » (Chuang-Tzu, ch. Ciel-Terre in François Chang- Vide et Plein. Le langage pictural chinois - Paris : Seuil, 1979).
Le vide est plein de tous les possibles.
« A l'origine, il y a le Rien (wu) ;
Le Rien n'a point de nom.
Du Rien est né l'Un ;
L'Un n'a point de forme. » (Tao Té King)
Le Un métaphysique n'est pas le un mathématique. Il en est de même pour le zéro : « le Zéro métaphysique n'est qu'un aspect de l'Infini ; du moins il nous est permis de le considérer comme tel en tant qu'il contient en principe l'unité, et par suite tout le reste. En effet, l'unité primordiale n'est que le Zéro affirmé, ou, en d'autres termes, l'Etre universel, qui est cette unité, n'est que le Non-être affirmé... ». (René Guénon, Les Etats multiples de l'Etre - Véga, Paris, 1980, p. 37-38)
L’abandon, au non de la raison et de la logique cartésienne de toute base métaphysique est-elle un progrès pour l’humanité ? A voir les conséquences, il est permis d’en douter. « Science sans conscience n’est que ruine de l’äme » écrivait Montaigne.
Emploi
Les nombres naturels permettent de compter les éléments d'un ensemble fini.
Propriété
(à faire)
Addition
Une addition consiste à ajouter un entier à un autre entier. Le résultat est appelé la somme.
- 0 est neutre pour l'addition: le résultat de la somme d'un nombre quelconque et de zéro donne ce même nombre.
:a+0=a
:5+0=5
:13+0=13
:4+0=4
- L'addition est commutative: l'ordre des termes de l'addition de deux termes ne change pas le résultat.
:a+b=b+a
:5+3=3+5
:8+4=4+8
:17+2=2+17
Multiplication
Le résultat d'une multiplication est appelé le produit.
- 1 est neutre pour la multiplication. Le résultat du produit d'un nombre quelconque par 1 donne ce même nombre.
:a × 1 = a
:5 × 1 = 5
:13 × 1 = 13
:4 × 1 = 4
- La multiplication est commutative. L'ordre des termes de la multiplication de deux termes ne change pas le résultat.
:a × b = b × a
:5 × 3 = 3 × 5
:8 × 4 = 4 × 8
:17 × 2 = 2 × 17
- Il y a plusieurs manières de définir la multiplication. Elle peut par exemple, être définie par récurrence comme itération de l'addition en posant :
:0×n=0
:m×(n+1)=m×n+m
Voir aussi
- La construction des entiers naturels
- Les nombres premiers
- Les nombres parfaits
- Les nombres quasi-parfaits
- Les nombres semi-parfaits
- Les nombres abondants
- Les nombres superabondants
- Les nombres amicaux
- Les nombres déficients
- Les nombres sociaux
- Les nombres amiables
- Les nombres chanceux
- Les nombres étranges
- Les nombres tordus
- Les nombres harmoniques
- Les nombres triangulaires
- Les nombres hexagonaux
- Les nombres figurés
- Les nombres chromatiques
- Le raisonnement par récurrence
- Les Axiomes de Peano
Catégorie:Nombre
ja:自然数
ko:자연수
th:จำนวนธรรมชาติ
Visual BasicCatégorie:Logiciel Microsoft
Catégorie:Environnement de développement intégré
Visual Basic est un environnement de développement intégré propriétaire pour le langage BASIC sous Windows, édité par Microsoft.
Historique
Visual Basic 1 est apparu en 1991. C'est à partir de la version 3, sortie en 1993 qu'il connaîtra le succès.
Le Visual Basic est une évolution des Basics précédents de Microsoft (Basica, GW Basic, QBasic) qui permet de créer des applications fenêtrées et de pratiquer donc la programmation événementielle. Bénéficiant de la simplicité du Basic originelle, il permet de créer des programmes relativement rapidement. Le programmeur en Visual Basic manipule des éléments visuels à l'écran auxquels il ne reste plus qu'à associer du code. On peut développer avec Visual Basic toutes sortes d'applications, qui peuvent notamment être intégrées dans les principaux logiciels Microsoft (Access, Excel, Word etc.)
Jusqu'à la version 4 de Visual Basic, il s'agissait d'un langage interprété, il a ensuite permis la génération de code binaire mais avec la nécessité de fournir toujours un fichier annexe de run-time (une bibliothèque dynamique, ou DLL).
Visual Basic n'est devenu un langage orienté objet qu'avec la version 7, plus couramment appelée Visual Basic .NET, qui peut quasiment être considérée comme un produit différent, tant les changements apportés ont été importants. La compatibilité des sources est cassée et la philosophie originale du basic (langage pour débutant) altérée sur l'autel du tout objet. Pour fonctionner cette dernière version nécessite l'installation du framework Microsoft .NET au lieu du runtime utilisé jusqu'à la version 6.
Autres Visual Basic
Microsoft a étendu le Visual Basic a de nombreuses applications :
- Visual Basic for Applications, langage de script utilisé dans la suite Microsoft Office.
- VBScript, langage de script concurrent de Javascript utilisé aussi bien côté serveur (ASP) ou côté client (dans Internet Explorer uniquement). Il est aussi utilisé pour des scripts évolués dans l'environnement Microsoft Windows.
Liens externes
- http://www.vbfrance.com/ : site de passionnés qui mettent en commun leurs connaissances.
- http://www.planetsourcecode.com/vb/ : mise en commun des ressources et connaissances.
- http://vb.developpez.com/ : Cours et tutoriels pour Visual Basic et VBA
- http://www.pise.info/vb : Cours et exercices pour débutants en Visual Basic
ja:Microsoft Visual Basic
ko:비주얼 베이직
ms:Visual Basic
simple:Visual Basic
th:วิชวลเบสิก
Récursion terminale
Idée
La récursion terminale est une méthode pour transformer, dans un programme, une récursion en itération : elle s'applique lorsque l'appel récursif dans une fonction est la dernière opération exécutée de cette fonction (ou encore : l'appel n'a pas d'enveloppe).
La récursion terminale est utilisée principalement dans les langages de programmation fonctionnels pour exprimer un processus itératif dans une forme fonctionnelle récursive. Les langages de programmation fonctionnels peuvent généralement détecter la récursion terminale et optimiser l'exécution de façon à itérer, en économisant ainsi l'espace de la pile d'appel, comme décrit ci-dessous.
Exemple
Prenons ce programme Scheme comme exemple :
(define (factorielle n)
(define (iterer n acc)
(if (<= n 1)
acc
(iterer (- n 1) (
- acc n))))
(iterer n 1))
On observe que la fonction 'iterer' s'appelle elle-même à la fin de sa définition. Cela permet à l'interpréteur ou au compilateur de réorganiser l'exécution, qui sans cela ressemblerait à ceci :
call factorielle (3)
call iterer (3 1)
call iterer (2 3)
call iterer (1 6)
call iterer (0 6)
retourne 6
retourne 6
retourne 6
retourne 6
retourne 6
après réorganisation :
call factorielle (3)
remplace les arguments avec (3 1), jump into « iterer »
remplace les arguments avec (2 3), re-iterer
remplace les arguments avec (1 6), re-iterer
remplace les arguments avec (0 6), re-iterer
retourne 6
(l'espace consommé est proportionnel à l'indentation)
Avantages
Cette réorganisation économise de l'espace car aucun état, sauf l'adresse de la fonction appelante, n'a besoin d'être sauvé sur la pile ou sur le tas. Cela signifie également que le programmeur n'a pas à craindre l'épuisement de l'espace de pile ou du tas pour des récursions très profondes.
Certains programmeurs utilisant des langages fonctionnels réécrivent du code récursif enveloppé de façon à tirer parti de cette caractéristique. Cela requiert souvent l'utilisation d'un accumulateur (acc dans l'implémentation ci-dessus de factorielle), comme argument de la fonction en récursion terminale. Dans certains cas (comme pour le filtrage de listes) et dans certains langages, la récursion terminale nécessite de réécrire une fonction dans un style non-fonctionnel : c'est-à-dire une fonction qui altère le contenu de variables passées en argument par référence.
Certains compilateurs utilisent une technique de réécriture de programme en « Continuation Passing Style » qui automatise la transformation d'une récursion enveloppée en récursion terminale. Associée à l'élimination d'appel terminal, cette technique permet d'optimiser le code produit pour des langages fonctionnels.
Pour finir, voici une version enveloppée de factorielle :
(define (factorielle n)
(cond ((= n 0) 1)
(else (
- n (factorielle (- n 1))))))
Le résultat de l'appel récursif (factorielle (- n 1)) est utilisé par la fonction
- , qui constitue ici l'enveloppe. À cause de cela, le résultat de (factorielle (- n 1)) doit être empilé pour être utilisé par
- . On ne peut économiser d'espace de pile.
Origines
Voir le papier de Guy Steele : ftp://publications.ai.mit.edu/ai-publications/0-499/AIM-443.ps
(librement traduit d'après la version anglophone)
Catégorie:Algorithmique
ja:末尾再帰
Catégorie:AlgorithmiqueCatégorie:Développement logicielcatégorie:Informatique théorique
L'algorithmique est la science des algorithmes. Elle vise à étudier les opérations nécessaires à la réalisation d'un calcul.
Cette catégorie réunit tous les articles autour de ce thème. Les algorithmes, fruits de l'algorithmique, sont rangés dans la catégorie algorithme.
En savoir plus sur l'algorithmique Wikipedia:Vekas danske artikkel/Veke 41, 2005
EU's historie starter i 1951 med underskrivelsen af Traktaten om Det europæiske kul- og stålfællesskab (EKSF/ECSC), og året senere, den 25. juli 1952 trådte det i kraft. Dette var et samarbejde der gik ud på at Frankrig og Tyskland slog deres administration af kul- og stålindustrien sammen. De fik Italien og Benelux-landene (Belgien, Nederlandene og Luxembourg) med. Dette samarbejde, som blev ledet af initiativtageren Jean Monnet, skulle blive forløberen til det vi i dag kender som EU.
Den 26. marts 1957 underskrev de samme seks lande, der oprettede Kul- og stålfællesskabet, den traktat som skulle blive en af de mest berømte i moderne europæisk historie, Rom-traktaten. Denne traktat blev en stor økonomisk fordel for medlemslandene, da den førte til at handelen mellem dem øgedes med næsten tredive procent blot i løbet af de første år. Meget af grundlaget for dette opsving i handelen, lå i oprettelsen af Det europæiske økonomiske fællesskab (EØF/EEC).
dieta praca w anglii konsultant slubny technologie NLP
|
|
|
|
