En informatique, la récursion terminale, aussi appelée, récursion finale, est un cas particulier de récursivité assimilée à une itération.
Une fonction à récursivité terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée. Cette instruction est alors nécessairement « pure », c'est-à-dire qu'elle consiste en un simple appel à la fonction, et jamais à un calcul ou une composition. Par exemple, dans un langage de programmation fictif :
fonction récursionTerminale(n) :
// ...
renvoie récursionTerminale(n - 1)
fonction récursionNonTerminale(n) :
// ...
renvoie n + récursionNonTerminale(n - 1)
récursionNonTerminale() n'est pas une récursion terminale car sa dernière instruction est une composition faisant intervenir l'appel récursif. Dans le premier cas, aucune référence aux résultats précédents n'est à conserver en mémoire, tandis que dans le second cas, tous les résultats intermédiaires doivent l'être. Les algorithmes récursifs exprimés à l'aide de fonctions à récursion terminale profitent donc d'une optimisation de la pile d'exécution.
Lors de la compilation (si elle existe), la récursion terminale peut être transformée en itération, c'est-à-dire en une série d'étapes séquentielles totalement dénuée de toute nature récursive.
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 (en général très condensée et « élégante »). Les langages de programmation fonctionnels peuvent généralement détecter la récursion terminale et optimiser son exécution en transformant la récursion en itération, économisant ainsi l'espace de la pile d'exécution, comme le montre l'exemple ci-dessous.
Prenons ce programme Scheme comme exemple :
(define (factorielle n)
(define (iterer n acc)
(if (
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Students learn several implementation techniques for modern functional and object-oriented programming languages. They put some of them into practice by developing key parts of a compiler and run time
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to u
In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Sussman and Guy L. Steele, Jr. coined the phrase in AI Memo 349 (1975), which sets out the first version of the Scheme programming language. John C. Reynolds gives a detailed account of the numerous discoveries of continuations.
En informatique, la récursion terminale, aussi appelée, récursion finale, est un cas particulier de récursivité assimilée à une itération. Une fonction à récursivité terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée. Cette instruction est alors nécessairement « pure », c'est-à-dire qu'elle consiste en un simple appel à la fonction, et jamais à un calcul ou une composition. Par exemple, dans un langage de programmation fictif : fonction récursionTerminale(n) : // ...
In computer programming, the word trampoline has a number of meanings, and is generally associated with jump instructions (i.e. moving to different code paths). Trampolines (sometimes referred to as indirect jump vectors) are memory locations holding addresses pointing to interrupt service routines, I/O routines, etc. Execution jumps into the trampoline and then immediately jumps out, or bounces, hence the term trampoline.
Couvre la génération de code pour un compilateur, traduisant un programme Amy à WebAssembly, y compris la gestion de la mémoire et la compilation de correspondance de motifs.