Un article de Wikipedia.y-project.com.

Sommaire 1 Introduction 1.1 Des exemples 1.2 La formalisation de la récursivité 2 Récursivité et informatique 2.1 Suppression de la récursivité 2.2 Acronymes récursifs 3 Liens externes

[] Introduction

La récursivité est le fait de décrire un processus dépendant de données, en faisant appel à ce même processus sur d'autres données plus «simples».

[] Des exemples

En mathématiques, on décrit couramment des objets par récursivité (même si ce n'est qu'un cas particulier simple d'application du principe de récurrence).

L'exemple classique d'une fonction définie récursivement est la factorielle n! :

<math>0! = 1\,</math>
<math>n! = n\ \times\ (n-1)!\ pour\ tout\ entier\ naturel\ n > 0\,</math>

ou encore :

<math>
f(n)=\left\ 1, & \mbox{si }n=0 \\ n\times f(n-1), & \mbox{si }n>0 \end\right.
</math>

Pour calculer f(3) ou 3! on procède ainsi:

<math>
\begin

f(3)& =& 3 \times f(3-1) \\ & =& 3 \times f(2)& =& 3 \times 2 \times f(2-1) \\ & & & =& 3 \times 2 \times f(1) & =& 3 \times 2 \times 1 \times f(1-1) \\ & & & & & =& 3 \times 2 \times 1 \times f(0)& =& 3 \times 2 \times 1 \times 1 \\ & & & & & & & =& 6

\end
</math>

Un autre grand classique est la suite des nombres de Fibonacci:

<math>fib(n) = \textrm n=0 \textrm 0 \textrm n=1 \textrm 1 \textrm fib(n-1)+fib(n-2).</math>

autrement dit:

<math>fib(0) = 0</math>
<math>fib(1) = 1</math>
<math>fib(n+2) = fib(n+1) + fib(n).</math>

[] La formalisation de la récursivité

Jusqu'au milieu des années trente, les mathématicines utilisaient des procédés récursifs sans le savoir. La formalisation du concept de récursivité est attribuée à Stephen Kleene, mais elle est le fruit d'une collaboration entre Gödel (qui en en avait besoin dans son théorème d'incomplétude), Church et Turing.

[] Récursivité et informatique

En informatique, une fonction qui contient un appel à elle-même est dite récursive. Il faut qu'elle comporte une condition d'arrêt, sinon le programme tourne indéfiniment. Cela permet de trouver une solution élégante et claire, même si ce n'est pas toujours la plus efficace, à certains problèmes - comme celui des Tours de Hanoï ou du tri arborescent. On parle alors d'algorithme récursif. Il existe également la récursivité croisée : c'est-à-dire plusieurs procédures ou fonctions peuvent s'appeler mutuellement.

[] Suppression de la récursivité

Des techniques existent pour remplacer une récursivité à gauche ou une récursivité à droite par un processus itératif plus économique. On peut alors définir par exemple une factorielle récursivement, tout en ayant l'assurance qu'au moment de son exécution elle sera exécutée autrement qu'avec de coûteux empilements de contextes d'appel. Voir Haskell.

La récursivité est étudiée par des langages de programmation théoriques comme la Récursion Primitive ou le Système T de Gödel par exemple.

[] Acronymes récursifs

La récursivité étant au c?ur de l'informatique, certains concepteurs facétieux ont créé des acronymes récursifs : le plus connu est GNU, dû à Richard Stallman, qui signifie « GNU is Not Unix », un autre est l'acronyme doublement récursif GNU Hurd.

• Hurd signifie Hird of Unix-replacing Daemons
• Hird signifie Hurd of Interfaces Representing Depth

[] Liens externes

• Un cours très complet sur la récursivitélt:Rekursija

DernierMirror  

Réagissez

Commentez l'encyclopédie:
Attention! tous les commentaites inaproprié seront supprimés

Titre:
Video YouTube ou google:	(doit être en rapport avec le sujet)
Votre mail:	(ne sera pas affiché sur le site)
Un pseudo:
Votre site:
Commentaire	(le html n'est pas autorisé, nombre de caractère maximum = 400)
	(Comment eBabylone 1.0 beta)

Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/récursivité