Récursivité (informatique) - Recursion (computer science)

Arbre créé à l'aide du langage de programmation Logo et s'appuyant fortement sur la récursivité. Chaque branche peut être considérée comme une version plus petite d'un arbre.

En informatique , la récursivité est une méthode de résolution d'un problème où la solution dépend de solutions à des instances plus petites du même problème. De tels problèmes peuvent généralement être résolus par itération , mais cela nécessite d'identifier et d'indexer les plus petites instances au moment de la programmation. La récursivité résout ces problèmes récursifs en utilisant des fonctions qui s'appellent elles-mêmes à partir de leur propre code. L'approche peut être appliquée à de nombreux types de problèmes, et la récursivité est l'une des idées centrales de l'informatique.

Le pouvoir de récursivité réside évidemment dans la possibilité de définir un ensemble infini d'objets par un énoncé fini. De la même manière, un nombre infini de calculs peut être décrit par un programme récursif fini, même si ce programme ne contient pas de répétitions explicites.

—  Niklaus Wirth , Algorithmes + Structures de données = Programmes , 1976

La plupart des langages de programmation informatique prennent en charge la récursivité en permettant à une fonction de s'appeler à partir de son propre code. Certains langages de programmation fonctionnels (par exemple, Clojure ) ne définissent aucune construction en boucle, mais reposent uniquement sur la récursivité pour appeler du code à plusieurs reprises. Il est prouvé en théorie de la calculabilité que ces langages récursifs seulement sont Turing complets ; cela signifie qu'ils sont aussi puissants (ils peuvent être utilisés pour résoudre les mêmes problèmes) que les langages impératifs basés sur des structures de contrôle telles que whileet for.

L'appel répété d'une fonction depuis elle-même peut amener la pile d'appels à avoir une taille égale à la somme des tailles d'entrée de tous les appels impliqués. Il s'ensuit que, pour les problèmes qui peuvent être résolus facilement par itération, la récursivité est généralement moins efficace , et, pour les gros problèmes, il est fondamental d'utiliser des techniques d'optimisation telles que l' optimisation des appels de queue .

Fonctions et algorithmes récursifs

Une tactique de programmation informatique courante consiste à diviser un problème en sous-problèmes du même type que l'original, à résoudre ces sous-problèmes et à combiner les résultats. C'est ce qu'on appelle souvent la méthode diviser pour régner ; lorsqu'il est combiné avec une table de recherche qui stocke les résultats des sous-problèmes précédemment résolus (pour éviter de les résoudre à plusieurs reprises et d'encourir un temps de calcul supplémentaire), il peut être appelé programmation dynamique ou mémorisation .

Cas de base

Une définition de fonction récursive a un ou plusieurs cas de base , c'est-à-dire une ou plusieurs entrées pour lesquelles la fonction produit un résultat trivialement (sans se répéter), et un ou plusieurs cas récursifs , c'est-à-dire une ou plusieurs entrées pour lesquelles le programme se répète (s'appelle lui-même) . Par exemple, la fonction factorielle peut être définie récursivement par les équations 0 ! = 1 et, pour tout n > 0 , n ! = n ( n − 1) ! . Aucune des deux équations en elle-même ne constitue une définition complète ; le premier est le cas de base et le second est le cas récursif. Parce que le cas de base rompt la chaîne de récursivité, il est parfois aussi appelé « cas de fin ».

Le travail des cas récursifs peut être vu comme la décomposition des entrées complexes en entrées plus simples. Dans une fonction récursive correctement conçue, à chaque appel récursif, le problème d'entrée doit être simplifié de telle manière qu'en fin de compte le cas de base doit être atteint. (Les fonctions qui ne sont pas destinées à se terminer dans des circonstances normales, par exemple certains processus système et serveur, font exception à cette règle.) Négliger d'écrire un cas de base ou le tester de manière incorrecte peut provoquer une boucle infinie .

Pour certaines fonctions (comme celle qui calcule la série pour e = 1/0! + 1/1! + 1/2! + 1/3! + ... ) il n'y a pas de cas de base évident impliqué par les données d'entrée ; pour ceux-ci, on peut ajouter un paramètre (tel que le nombre de termes à ajouter, dans notre exemple de série) pour fournir un « critère d'arrêt » qui établit le cas de base. Un tel exemple est plus naturellement traité par corecursion , où les termes successifs dans la sortie sont les sommes partielles ; cela peut être converti en une récursivité en utilisant le paramètre d'indexation pour dire "calculer le n ème terme ( n ème somme partielle)".

Types de données récursives

De nombreux programmes informatiques doivent traiter ou générer une quantité arbitrairement importante de données . La récursion est une technique de représentation de données dont la taille exacte est inconnue du programmeur : le programmeur peut spécifier ces données avec une définition autoréférentielle . Il existe deux types de définitions autoréférentielles : les définitions inductives et coinductives .

Données définies de manière inductive

Une définition de données récursive définie de manière inductive est une définition qui spécifie comment construire des instances des données. Par exemple, les listes chaînées peuvent être définies de manière inductive (ici, en utilisant la syntaxe Haskell ) :

data ListOfStrings = EmptyList | Cons String ListOfStrings

Le code ci-dessus spécifie une liste de chaînes soit vide, soit une structure contenant une chaîne et une liste de chaînes. L'auto-référence dans la définition permet la construction de listes de n'importe quel nombre (fini) de chaînes.

Un autre exemple de définition inductive est les nombres naturels (ou entiers positifs ):

A natural number is either 1 or n+1, where n is a natural number.

De même, des définitions récursives sont souvent utilisées pour modéliser la structure des expressions et des instructions dans les langages de programmation. Les concepteurs de langages expriment souvent des grammaires dans une syntaxe telle que la forme Backus-Naur ; voici une telle grammaire, pour un langage simple d'expressions arithmétiques avec multiplication et addition :

 <expr> ::= <number>
          | (<expr> * <expr>)
          | (<expr> + <expr>)

Cela dit qu'une expression est soit un nombre, un produit de deux expressions ou une somme de deux expressions. En se référant de manière récursive aux expressions des deuxième et troisième lignes, la grammaire autorise des expressions arithmétiques arbitrairement compliquées telles que (5 * ((3 * 6) + 8)), avec plus d'une opération de produit ou de somme dans une seule expression.

Données définies de manière coinductive et corecursion

Une définition de données coductive est une définition qui spécifie les opérations qui peuvent être effectuées sur une donnée ; typiquement, des définitions co-référentielles auto-référentielles sont utilisées pour des structures de données de taille infinie.

Une définition coductive de flux infinis de chaînes, donnée de manière informelle, pourrait ressembler à ceci :

A stream of strings is an object s such that:
 head(s) is a string, and
 tail(s) is a stream of strings.

Ceci est très similaire à une définition inductive de listes de chaînes ; la différence est que cette spécifie définition comment accéder au contenu des données structure à savoir, via les accesseurs fonctions headet tail-et ce que ces contenus peuvent être, alors que les Précise de définition inductives comment créer la structure et ce qu'il peut être créé à partir.

La corecursion est liée à la coinduction et peut être utilisée pour calculer des instances particulières d'objets (éventuellement) infinis. En tant que technique de programmation, il est le plus souvent utilisé dans le contexte des langages de programmation paresseux et peut être préférable à la récursivité lorsque la taille ou la précision souhaitée de la sortie d'un programme est inconnue. Dans de tels cas, le programme nécessite à la fois une définition pour un résultat infiniment grand (ou infiniment précis) et un mécanisme pour prendre une partie finie de ce résultat. Le problème du calcul des n premiers nombres premiers est un problème qui peut être résolu avec un programme corecursif (par exemple ici ).

Types de récursivité

Récursivité simple et récursivité multiple

La récursivité qui ne contient qu'une seule auto-référence est appelée récursivité unique , tandis que la récursivité qui contient plusieurs auto-références est connue sous le nomrécursivité multiple . Les exemples standard de récursivité unique incluent la traversée de liste, comme dans une recherche linéaire, ou le calcul de la fonction factorielle, tandis que les exemples standard de récursivité multiple incluentla traversée d'arbre, comme dans une recherche en profondeur d'abord.

La récursivité simple est souvent beaucoup plus efficace que la récursivité multiple, et peut généralement être remplacée par un calcul itératif, s'exécutant en temps linéaire et nécessitant un espace constant. La récursivité multiple, en revanche, peut nécessiter un temps et un espace exponentiels, et est plus fondamentalement récursive, ne pouvant pas être remplacée par une itération sans pile explicite.

La récursivité multiple peut parfois être convertie en récursivité unique (et, si vous le souhaitez, en itération). Par exemple, alors que le calcul de la séquence de Fibonacci est naïvement une itération multiple, comme chaque valeur nécessite deux valeurs précédentes, elle peut être calculée par récursivité unique en passant deux valeurs successives en paramètres. Ceci est plus naturellement encadré comme corecursion, construit à partir des valeurs initiales, suivant à chaque étape deux valeurs successives – voir corecursion : exemples . Un exemple plus sophistiqué consiste à utiliser un arbre binaire fileté , qui permet une traversée itérative de l'arbre, plutôt que la récursivité multiple.

Récursion indirecte

La plupart des exemples de base de récursivité, et la plupart des exemples présentés ici, démontrent récursivité directe , dans laquelle une fonction s'appelle elle-même. La récursivité indirecte se produit lorsqu'une fonction n'est pas appelée par elle-même mais par une autre fonction qu'elle a appelée (directement ou indirectement). Par exemple, si f appelle f, c'est la récursivité directe, mais si f appelle g qui appelle f, alors c'est la récursivité indirecte de f. Des chaînes de trois fonctions ou plus sont possibles ; par exemple, la fonction 1 appelle la fonction 2, la fonction 2 appelle la fonction 3 et la fonction 3 appelle à nouveau la fonction 1.

La récursivité indirecte est également appelée récursion mutuelle , qui est un terme plus symétrique, bien qu'il s'agisse simplement d'une différence d'accent, pas d'une notion différente. Autrement dit, si f appelle g et alors g appelle f, qui à son tour appelle à nouveau g , du point de vue de f seul, f est indirectement récursif, tandis que du point de vue de g seul, il est indirectement récursif, tandis que du point de vue des deux, f et g se reproduisent mutuellement. De même, un ensemble de trois fonctions ou plus qui s'appellent peut être appelé un ensemble de fonctions mutuellement récursives.

Récursion anonyme

La récursivité est généralement effectuée en appelant explicitement une fonction par son nom. Cependant, la récursivité peut également être effectuée en appelant implicitement une fonction basée sur le contexte actuel, ce qui est particulièrement utile pour les fonctions anonymes , et est connue sous le nom de récursivité anonyme .

Récursion structurelle contre récursivité générative

Certains auteurs classent la récursivité comme « structurelle » ou « générative ». La distinction est liée à l'endroit où une procédure récursive obtient les données sur lesquelles elle travaille et à la manière dont elle traite ces données :

[Les fonctions qui consomment des données structurées] décomposent généralement leurs arguments en leurs composants structurels immédiats, puis traitent ces composants. Si l'un des composants immédiats appartient à la même classe de données que l'entrée, la fonction est récursive. Pour cette raison, nous appelons ces fonctions des FONCTIONS (STRUCTURELLEMENT) RÉCURSIVES.

—  Felleisen, Findler, Flatt et Krishnaurthi, Comment concevoir des programmes , 2001

Ainsi, la caractéristique déterminante d'une fonction structurellement récursive est que l'argument de chaque appel récursif est le contenu d'un champ de l'entrée d'origine. La récursivité structurelle inclut presque tous les parcours d'arbres, y compris le traitement XML, la création et la recherche d'arbres binaires, etc. En considérant la structure algébrique des nombres naturels (c'est-à-dire qu'un nombre naturel est soit zéro, soit le successeur d'un nombre naturel), des fonctions telles comme factorielle peut également être considérée comme une récursivité structurelle.

La récursivité générative est l'alternative :

De nombreux algorithmes récursifs bien connus génèrent une toute nouvelle donnée à partir des données données et se répètent dessus. HtDP ( How to Design Programs ) désigne ce type de récursivité générative. Les exemples de récursivité générative incluent : gcd , quicksort , binary search , mergesort , la méthode de Newton , les fractales et l' intégration adaptative .

—  Matthias Felleisen, Programmation fonctionnelle avancée , 2002

Cette distinction est importante pour prouver la terminaison d'une fonction.

  • On peut facilement montrer que toutes les fonctions structurellement récursives sur des structures de données finies ( définies par induction ) se terminent, via l' induction structurelle : intuitivement, chaque appel récursif reçoit un plus petit morceau de données d'entrée, jusqu'à ce qu'un cas de base soit atteint.
  • Les fonctions générativement récursives, en revanche, ne fournissent pas nécessairement une entrée plus petite à leurs appels récursifs, de sorte que la preuve de leur terminaison n'est pas nécessairement aussi simple, et éviter les boucles infinies nécessite une plus grande prudence. Ces fonctions générativement récursives peuvent souvent être interprétées comme des fonctions corecursives - chaque étape génère les nouvelles données, telles que les approximations successives dans la méthode de Newton - et mettre fin à cette corecursion nécessite que les données satisfassent finalement à une condition, qui n'est pas nécessairement garantie.
  • En termes de variantes de boucle , la récursivité structurelle se produit lorsqu'il existe une variante de boucle évidente, à savoir la taille ou la complexité, qui commence finie et diminue à chaque étape récursive.
  • En revanche, la récursivité générative se produit lorsqu'il n'y a pas une variante de boucle aussi évidente, et la terminaison dépend d'une fonction, telle que "l'erreur d'approximation" qui ne diminue pas nécessairement jusqu'à zéro, et donc la terminaison n'est pas garantie sans une analyse plus approfondie.

Problèmes de mise en œuvre

Dans la mise en œuvre réelle, plutôt qu'une fonction récursive pure (vérification unique pour le cas de base, sinon étape récursive), un certain nombre de modifications peuvent être apportées, à des fins de clarté ou d'efficacité. Ceux-ci inclus:

  • Fonction wrapper (en haut)
  • Court-circuiter le cas de base, alias "Récursivité sans lien de dépendance" (en bas)
  • Algorithme hybride (en bas) - passer à un algorithme différent une fois que les données sont suffisamment petites

Sur la base de l'élégance, les fonctions d'emballage sont généralement approuvées, tandis que le court-circuit du boîtier de base est mal vu, en particulier dans le monde universitaire. Les algorithmes hybrides sont souvent utilisés pour plus d'efficacité, pour réduire la surcharge de récursivité dans les petits cas, et la récursivité sans lien de dépendance en est un cas particulier.

Fonction d'emballage

Une fonction wrapper est une fonction qui est appelée directement mais ne se récure pas elle-même, appelant à la place une fonction auxiliaire distincte qui effectue réellement la récursivité.

Les fonctions wrapper peuvent être utilisées pour valider des paramètres (afin que la fonction récursive puisse les ignorer), effectuer une initialisation (allouer de la mémoire, initialiser des variables), en particulier pour des variables auxiliaires telles que le "niveau de récursivité" ou des calculs partiels pour la mémorisation , et gérer les exceptions et les erreurs . Dans les langages qui prennent en charge les fonctions imbriquées , la fonction auxiliaire peut être imbriquée dans la fonction wrapper et utiliser une portée partagée. En l'absence de fonctions imbriquées, les fonctions auxiliaires sont plutôt une fonction distincte, si possible privée (car elles ne sont pas appelées directement), et les informations sont partagées avec la fonction wrapper en utilisant pass-by-reference .

Court-circuiter le cas de base

Factorielle : ordinaire vs court-circuit
Récursivité ordinaire Récursivité de court-circuit
int fac1(int n) {
   if (n <= 0)
      return 1;
   else
      return fac1(n-1)*n;
}
static int fac2(int n) {
   // assert(n >= 2);
   if (n == 2)
      return 2;
   else
      return fac2(n-1)*n;
}
int fac2wrapper(int n) {
   if (n <= 1)
      return 1;
   else
      return fac2(n);
}

Court-circuiter le cas de base, également connu sous le nom de récursivité sans lien de dépendance , consiste à vérifier le cas de base avant de faire un appel récursif - c'est-à-dire vérifier si le prochain appel sera le cas de base, au lieu d'appeler puis de vérifier le cas de base . Le court-circuit est notamment fait pour des raisons d'efficacité, pour éviter le surcoût d'un appel de fonction qui retourne immédiatement. Notez que puisque le cas de base a déjà été vérifié (immédiatement avant l'étape récursive), il n'a pas besoin d'être vérifié séparément, mais il faut utiliser une fonction wrapper pour le cas où la récursivité globale commence par le cas de base lui-même. Par exemple, dans la fonction factorielle, correctement le cas de base est 0 ! = 1, en retournant immédiatement 1 pour 1 ! est un court-circuit et peut manquer 0 ; cela peut être atténué par une fonction wrapper. La boîte montre le code C pour raccourcir les cas factoriels 0 et 1.

Le court-circuit est principalement un problème lorsque de nombreux cas de base sont rencontrés, tels que les pointeurs Null dans un arbre, qui peuvent être linéaires dans le nombre d'appels de fonction, d'où des économies importantes pour les algorithmes O ( n ) ; ceci est illustré ci-dessous pour une recherche en profondeur d'abord. Court-circuiter sur un arbre correspond à considérer une feuille (nœud non vide sans enfant) comme cas de base, plutôt que de considérer un nœud vide comme cas de base. S'il n'y a qu'un seul cas de base, comme dans le calcul de la factorielle, le court-circuit ne fournit que des économies de O (1) .

Conceptuellement, le court-circuit peut être considéré comme ayant le même cas de base et la même étape récursive, en vérifiant le cas de base uniquement avant la récursivité, ou il peut être considéré comme ayant un cas de base différent (une étape retirée du cas de base standard) et un étape récursive plus complexe, à savoir « check valid then recurse », comme en considérant les nœuds feuilles plutôt que les nœuds nuls comme cas de base dans un arbre. Parce que le court-circuit a un flux plus compliqué, comparé à la séparation claire du cas de base et de l'étape récursive dans la récursivité standard, il est souvent considéré comme un style médiocre, en particulier dans le milieu universitaire.

Recherche en profondeur

Un exemple basique de court-circuit est donné dans la recherche en profondeur d'abord (DFS) d'un arbre binaire ; voir la section des arbres binaires pour une discussion récursive standard.

L'algorithme récursif standard pour un DFS est :

  • cas de base : si le nœud actuel est Null, renvoie false
  • étape récursive : sinon, vérifie la valeur du nœud actuel, renvoie true si elle correspond, sinon récurse sur les enfants

En court-circuit, c'est plutôt :

  • vérifier la valeur du nœud actuel, retourner vrai si correspondance,
  • sinon, sur les enfants, sinon Null, alors récursif.

En termes d'étapes standard, cela déplace la vérification du cas de base avant l'étape récursive. Alternativement, ceux-ci peuvent être considérés comme une forme différente de cas de base et d'étape récursive, respectivement. Notez que cela nécessite une fonction wrapper pour gérer le cas où l'arbre lui-même est vide (le nœud racine est Null).

Dans le cas d'un arbre binaire parfait de hauteur h, il y a 2 h +1 −1 nœuds et 2 h +1 pointeurs nuls comme enfants (2 pour chacune des 2 h feuilles), donc le court-circuit coupe le nombre de fonction appelle de moitié dans le pire des cas.

En C, l'algorithme récursif standard peut être implémenté comme :

bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // base case
    else if (tree_node->data == i)
        return true;
    else
        return tree_contains(tree_node->left, i) ||
               tree_contains(tree_node->right, i);
}

L'algorithme court-circuité peut être implémenté comme :

// Wrapper function to handle empty tree
bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // empty tree
    else
        return tree_contains_do(tree_node, i);  // call auxiliary function
}

// Assumes tree_node != NULL
bool tree_contains_do(struct node *tree_node, int i) {
    if (tree_node->data == i)
        return true;  // found
    else  // recurse
        return (tree_node->left  && tree_contains_do(tree_node->left,  i)) ||
               (tree_node->right && tree_contains_do(tree_node->right, i));
}

Notez l'utilisation de l' évaluation de court-circuit des opérateurs booléens && (AND), de sorte que l'appel récursif n'est effectué que si le nœud est valide (non-Null). Notez que tandis que le premier terme de l'AND est un pointeur vers un nœud, le deuxième terme est un booléen, donc l'expression globale est évaluée à un booléen. C'est un idiome courant dans le court-circuit récursif. Ceci s'ajoute à l'évaluation de court-circuit du booléen || (OR) pour vérifier uniquement l'enfant de droite si l'enfant de gauche échoue. En fait, l'ensemble du flux de contrôle de ces fonctions peut être remplacé par une seule expression booléenne dans une instruction return, mais la lisibilité ne souffre d'aucun avantage en termes d'efficacité.

Algorithme hybride

Les algorithmes récursifs sont souvent inefficaces pour les petites données, en raison de la surcharge des appels et retours de fonction répétés. Pour cette raison, les implémentations efficaces d'algorithmes récursifs commencent souvent par l'algorithme récursif, mais passent ensuite à un algorithme différent lorsque l'entrée devient petite. Un exemple important est le tri par fusion , qui est souvent implémenté en passant au tri par insertion non récursif lorsque les données sont suffisamment petites, comme dans le tri par fusion en mosaïque . Les algorithmes récursifs hybrides peuvent souvent être affinés davantage, comme dans Timsort , dérivés d'un tri par fusion/tri par insertion hybride.

Récursivité versus itération

La récursivité et l' itération sont également expressives : la récursivité peut être remplacée par l'itération avec une pile d'appels explicite , tandis que l'itération peut être remplacée par la récursivité de queue . L'approche à privilégier dépend du problème considéré et du langage utilisé. En programmation impérative , l'itération est préférée, en particulier pour la récursivité simple, car elle évite la surcharge des appels de fonction et la gestion de la pile d'appels, mais la récursivité est généralement utilisée pour la récursivité multiple. En revanche, dans les langages fonctionnels, la récursivité est préférée, l'optimisation de la récursivité de la queue entraînant peu de surcharge. L'implémentation d'un algorithme par itération peut ne pas être facilement réalisable.

Comparez les modèles pour calculer x n défini par x n = f(n, x n-1 ) à partir de x base :

function recursive(n)
    if n == base
        return xbase
    else
        return f(n, recursive(n-1))
function iterative(n)
    x = xbase
    for i = base+1 to n
        x = f(i, x)
    return x

Pour le langage impératif, le surcoût consiste à définir la fonction, pour le langage fonctionnel, le surcoût consiste à définir la variable d'accumulateur x.

Par exemple, une fonction factorielle peut être implémentée de manière itérative en C en affectant à une variable d'index de boucle et à une variable d'accumulateur, plutôt qu'en passant des arguments et en retournant des valeurs par récursivité :

unsigned int factorial(unsigned int n) {
  unsigned int product = 1; // empty product is 1
  while (n) {
    product *= n;
    --n;
  }
  return product;
}

Puissance expressive

La plupart des langages de programmation utilisés aujourd'hui permettent la spécification directe de fonctions et de procédures récursives. Lorsqu'une telle fonction est appelée, l' environnement d'exécution du programme garde une trace des différentes instances de la fonction (souvent en utilisant une pile d'appels , bien que d'autres méthodes puissent être utilisées). Chaque fonction récursive peut être transformée en une fonction itérative en remplaçant les appels récursifs par des constructions de contrôle itératives et en simulant la pile d'appels avec une pile explicitement gérée par le programme.

Inversement, toutes les fonctions et procédures itératives qui peuvent être évaluées par un ordinateur (voir Complétude de Turing ) peuvent être exprimées en termes de fonctions récursives ; les constructions de contrôle itératives telles que les boucles while et for sont régulièrement réécrites sous forme récursive dans les langages fonctionnels . Cependant, en pratique, cette réécriture dépend de l' élimination des appels de queue , ce qui n'est pas une caractéristique de tous les langages. C , Java et Python sont des langages courants notables dans lesquels tous les appels de fonction, y compris les appels de queue , peuvent entraîner une allocation de pile qui ne se produirait pas avec l'utilisation de constructions en boucle ; dans ces langages, un programme itératif fonctionnel réécrit sous une forme récursive peut déborder la pile d'appels , bien que l'élimination des appels de queue puisse être une fonctionnalité qui n'est pas couverte par la spécification d'un langage, et différentes implémentations du même langage peuvent différer dans les capacités d'élimination des appels de queue.

Les problèmes de performance

Dans les langages (tels que C et Java ) qui favorisent les constructions de boucle itérative, les programmes récursifs sont généralement associés à des coûts de temps et d'espace importants, en raison de la surcharge nécessaire pour gérer la pile et de la lenteur relative des appels de fonction ; dans les langages fonctionnels , un appel de fonction (en particulier un appel de queue ) est généralement une opération très rapide, et la différence est généralement moins perceptible.

A titre d'exemple concret, la différence de performances entre les implémentations récursives et itératives de l'exemple "factoriel" ci-dessus dépend fortement du compilateur utilisé. Dans les langages où les constructions en boucle sont préférées, la version itérative peut être jusqu'à plusieurs ordres de grandeur plus rapide que la version récursive. Dans les langages fonctionnels, la différence de temps globale des deux implémentations peut être négligeable ; en fait, le coût de multiplier d'abord les plus grands nombres plutôt que les plus petits (ce que fait la version itérative donnée ici) peut dépasser le temps gagné en choisissant l'itération.

Espace de pile

Dans certains langages de programmation, la taille maximale de la pile d'appels est bien inférieure à l'espace disponible dans le tas , et les algorithmes récursifs ont tendance à nécessiter plus d'espace de pile que les algorithmes itératifs. Par conséquent, ces langages imposent parfois une limite sur la profondeur de récursivité pour éviter les débordements de pile ; Python est l'un de ces langages. Notez la mise en garde ci-dessous concernant le cas particulier de la récursivité de la queue .

Vulnérabilité

Étant donné que les algorithmes récursifs peuvent être sujets à des débordements de pile, ils peuvent être vulnérables aux entrées pathologiques ou malveillantes . Certains logiciels malveillants ciblent spécifiquement la pile d'appels d'un programme et tirent parti de la nature intrinsèquement récursive de la pile. Même en l'absence de malware, un débordement de pile causé par une récursivité illimitée peut être fatal au programme, et la logique de gestion des exceptions peut ne pas empêcher l' arrêt du processus correspondant .

Multiplier les problèmes récursifs

Les problèmes de multiplication récursive sont intrinsèquement récursifs, en raison de l'état antérieur qu'ils doivent suivre. Un exemple est la traversée d'arbres comme dans la recherche en profondeur d'abord ; bien que des méthodes récursives et itératives soient utilisées, elles contrastent avec le parcours de liste et la recherche linéaire dans une liste, qui est une méthode uniquement récursive et donc naturellement itérative. D'autres exemples incluent des algorithmes diviser pour régner tels que Quicksort et des fonctions telles que la fonction Ackermann . Tous ces algorithmes peuvent être implémentés de manière itérative à l'aide d'une pile explicite , mais l'effort du programmeur impliqué dans la gestion de la pile et la complexité du programme résultant l'emportent sans doute sur les avantages de la solution itérative.

Refactorisation de la récursivité

Les algorithmes récursifs peuvent être remplacés par des équivalents non récursifs. Une méthode pour remplacer les algorithmes récursifs consiste à les simuler en utilisant la mémoire de tas au lieu de la mémoire de pile . Une alternative consiste à développer un algorithme de remplacement entièrement basé sur des méthodes non récursives, ce qui peut être difficile. Par exemple, les algorithmes récursifs pour les caractères génériques correspondants , tels que Rich Salz ' wildmat algorithme, ont été une fois typique. Des algorithmes non récursifs dans le même but, tels que l' algorithme de correspondance des caractères génériques de Krauss , ont été développés pour éviter les inconvénients de la récursivité et ne se sont améliorés que progressivement en fonction de techniques telles que la collecte de tests et le profilage des performances.

Fonctions de queue récursive

Les fonctions récursives de queue sont des fonctions dans lesquelles tous les appels récursifs sont des appels de queue et ne construisent donc pas d'opérations différées. Par exemple, la fonction gcd (représentée ci-dessous) est récursive en queue. En revanche, la fonction factorielle (également ci-dessous) n'est pas récursive de queue ; parce que son appel récursif n'est pas en position de queue, il construit des opérations de multiplication différées qui doivent être effectuées une fois l'appel récursif final terminé. Avec un compilateur ou un interpréteur qui traite les appels récursifs de queue comme des sauts plutôt que des appels de fonction, une fonction récursive de queue telle que gcd s'exécutera en utilisant un espace constant. Ainsi, le programme est essentiellement itératif, équivalent à l'utilisation de structures de contrôle de langage impératif comme les boucles "for" et "while".

Récursivité de queue : Augmentation de la récursivité :
//INPUT: Integers x, y such that x >= y and y >= 0
int gcd(int x, int y)
{
  if (y == 0)
     return x;
  else
     return gcd(y, x % y);
}
//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
   if (n == 0)
      return 1;
   else
      return n * fact(n - 1);
}

L'importance de la récursivité de queue est que lors d'un appel récursif de queue (ou n'importe quel appel de queue), la position de retour de l'appelant n'a pas besoin d'être sauvegardée sur la pile d'appels ; lorsque l'appel récursif revient, il se branche directement sur la position de retour précédemment enregistrée. Par conséquent, dans les langages qui reconnaissent cette propriété des appels de queue, la récursivité de queue économise à la fois de l'espace et du temps.

Ordre d'exécution

Considérez ces deux fonctions :

Fonction 1

void recursiveFunction(int num) {
    printf("%d\n", num);
    if (num < 4)
        recursiveFunction(num + 1);
}

Récursif1.svg

Fonction 2

void recursiveFunction(int num) {
    if (num < 4)
        recursiveFunction(num + 1);
    printf("%d\n", num);
}

Récursive2.svg

La fonction 2 est la fonction 1 avec les lignes interverties.

Dans le cas d'une fonction ne s'appelant qu'une seule fois, les instructions placées avant l'appel récursif sont exécutées une fois par récursivité avant l'une quelconque des instructions placées après l'appel récursif. Ces derniers sont exécutés à plusieurs reprises après que la récursivité maximale a été atteinte.

Notez également que l' ordre des instructions d'impression est inversé, ce qui est dû à la façon dont les fonctions et les instructions sont stockées sur la pile d'appels .

Procédures récursives

Factorielle

Un exemple classique de procédure récursive est la fonction utilisée pour calculer la factorielle d'un nombre naturel :

Pseudocode (récursif) :
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ]
end factorial

La fonction peut aussi s'écrire sous la forme d' une relation de récurrence :

Cette évaluation de la relation de récurrence démontre le calcul qui serait effectué en évaluant le pseudocode ci-dessus :

Calcul de la relation de récurrence pour n = 4 :
b4           = 4 × b3
             = 4 × (3 × b2)
             = 4 × (3 × (2 × b1))
             = 4 × (3 × (2 × (1 × b0)))
             = 4 × (3 × (2 × (1 × 1)))
             = 4 × (3 × (2 × 1))
             = 4 × (3 × 2)
             = 4 × 6
             = 24

Cette fonction factorielle peut également être décrite sans utiliser la récursivité en utilisant les constructions de boucle typiques trouvées dans les langages de programmation impératifs :

Pseudocode (itératif) :
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. create new variable called running_total with a value of 1
2. begin loop 1. if n is 0, exit loop 2. set running_total to (running_total × n) 3. decrement n 4. repeat loop
3. return running_total
end factorial

Le code impératif ci-dessus est équivalent à cette définition mathématique utilisant une variable d'accumulateur t :

La définition ci-dessus se traduit directement par des langages de programmation fonctionnels tels que Scheme ; c'est un exemple d'itération implémentée récursivement.

Plus grand diviseur commun

L' algorithme d'Euclide , qui calcule le plus grand diviseur commun de deux entiers, peut s'écrire récursivement.

Définition de la fonction :

Pseudocode (récursif) :
function gcd is:
input: integer x, integer y such that x > 0 and y >= 0

1. if y is 0, return x 2. otherwise, return [ gcd( y, (remainder of x/y) ) ]
end gcd

Relation de récurrence pour le plus grand commun diviseur, où exprime le reste de :

si
Calcul de la relation de récurrence pour x = 27 et y = 9 :
gcd(27, 9)   = gcd(9, 27 % 9)
             = gcd(9, 0)
             = 9
Calcul de la relation de récurrence pour x = 111 et y = 259 :
gcd(111, 259)   = gcd(259, 111 % 259)
                = gcd(259, 111)
                = gcd(111, 259 % 111)
                = gcd(111, 37)
                = gcd(37, 111 % 37)
                = gcd(37, 0)
                = 37

Le programme récursif ci-dessus est récursif en queue ; c'est équivalent à un algorithme itératif, et le calcul montré ci-dessus montre les étapes d'évaluation qui seraient effectuées par un langage qui élimine les appels de queue. Vous trouverez ci-dessous une version du même algorithme utilisant une itération explicite, adaptée à un langage qui n'élimine pas les appels de queue. En maintenant son état entièrement dans les variables x et y et en utilisant une construction en boucle, le programme évite de faire des appels récursifs et d'augmenter la pile d'appels.

Pseudocode (itératif) :
function gcd is:
input: integer x, integer y such that x >= y and y >= 0
1. create new variable called remainder
2. begin loop 1. if y is zero, exit loop 2. set remainder to the remainder of x/y 3. set x to y 4. set y to remainder 5. repeat loop
3. return x
end gcd

L'algorithme itératif nécessite une variable temporaire, et même étant donné la connaissance de l'algorithme euclidien, il est plus difficile de comprendre le processus par simple inspection, bien que les deux algorithmes soient très similaires dans leurs étapes.

Tours de Hanoï

Tours de Hanoï

Les Tours de Hanoï est un puzzle mathématique dont la solution illustre la récursivité. Il y a trois chevilles qui peuvent contenir des piles de disques de différents diamètres. Un disque plus grand ne peut jamais être empilé sur un plus petit. En commençant par n disques sur un piquet, ils doivent être déplacés un à un sur un autre piquet. Quel est le plus petit nombre d'étapes pour déplacer la pile ?

Définition de la fonction :

Relation de récurrence pour hanoi :

Calcul de la relation de récurrence pour n = 4 :
hanoi(4)     = 2×hanoi(3) + 1
             = 2×(2×hanoi(2) + 1) + 1
             = 2×(2×(2×hanoi(1) + 1) + 1) + 1
             = 2×(2×(2×1 + 1) + 1) + 1
             = 2×(2×(3) + 1) + 1
             = 2×(7) + 1
             = 15


Exemples d'implémentations :

Pseudocode (récursif) :
function hanoi is:
input: integer n, such that n >= 1
1. if n is 1 then return 1
2. return [2 * [call hanoi(n-1)] + 1]
end hanoi

Bien que toutes les fonctions récursives n'aient pas de solution explicite, la séquence de la tour de Hanoï peut être réduite à une formule explicite.

Une formule explicite pour les Tours de Hanoï :
h1 = 1   = 21 - 1
h2 = 3   = 22 - 1
h3 = 7   = 23 - 1
h4 = 15  = 24 - 1
h5 = 31  = 25 - 1
h6 = 63  = 26 - 1
h7 = 127 = 27 - 1
In general:
hn = 2n - 1, for all n >= 1

Recherche binaire

L' algorithme de recherche binaire est une méthode de recherche d'un tableau trié pour un seul élément en coupant le tableau en deux à chaque passage récursif. L'astuce consiste à choisir un point médian près du centre du tableau, à comparer les données à ce point avec les données recherchées, puis à répondre à l'une des trois conditions possibles : les données se trouvent au point médian, les données au point médian sont supérieures que les données recherchées, ou les données au milieu sont inférieures aux données recherchées.

La récursivité est utilisée dans cet algorithme car à chaque passage, un nouveau tableau est créé en coupant l'ancien en deux. La procédure de recherche binaire est ensuite appelée de manière récursive, cette fois sur le nouveau (et plus petit) tableau. Généralement, la taille du tableau est ajustée en manipulant un index de début et de fin. L'algorithme présente un ordre de croissance logarithmique car il divise essentiellement le domaine du problème en deux à chaque passage.

Exemple d'implémentation de la recherche binaire en C :

 /*
  Call binary_search with proper initial conditions.

  INPUT:
    data is an array of integers SORTED in ASCENDING order,
    toFind is the integer to search for,
    count is the total number of elements in the array

  OUTPUT:
    result of binary_search

 */
 int search(int *data, int toFind, int count)
 {
    //  Start = 0 (beginning index)
    //  End = count - 1 (top index)
    return binary_search(data, toFind, 0, count-1);
 }

 /*
   Binary Search Algorithm.

   INPUT:
        data is a array of integers SORTED in ASCENDING order,
        toFind is the integer to search for,
        start is the minimum array index,
        end is the maximum array index
   OUTPUT:
        position of the integer toFind within array data,
        -1 if not found
 */
 int binary_search(int *data, int toFind, int start, int end)
 {
    //Get the midpoint.
    int mid = start + (end - start)/2;   //Integer division


    if (start > end)                     //Stop condition (base case)
       return -1;
    else if (data[mid] == toFind)        //Found, return index
       return mid;
    else if (data[mid] > toFind)         //Data is greater than toFind, search lower half
       return binary_search(data, toFind, start, mid-1);
    else                                 //Data is less than toFind, search upper half
       return binary_search(data, toFind, mid+1, end);
 }

Structures de données récursives (récursivité structurelle)

Une application importante de la récursivité en informatique consiste à définir des structures de données dynamiques telles que des listes et des arbres . Les structures de données récursives peuvent croître dynamiquement jusqu'à une taille théoriquement infinie en réponse aux exigences d'exécution ; en revanche, la taille d'un tableau statique doit être définie au moment de la compilation.

"Les algorithmes récursifs sont particulièrement appropriés lorsque le problème sous-jacent ou les données à traiter sont définis en termes récursifs."

Les exemples de cette section illustrent ce que l'on appelle la "récursion structurelle". Ce terme fait référence au fait que les procédures récursives agissent sur des données définies de manière récursive.

Tant qu'un programmeur dérive le modèle d'une définition de données, les fonctions utilisent la récursivité structurelle. C'est-à-dire que les récursions dans le corps d'une fonction consomment une partie immédiate d'une valeur composée donnée.

Listes liées

Vous trouverez ci-dessous une définition en C d'une structure de nœuds de liste chaînée. Remarquez en particulier comment le nœud est défini en termes de lui-même. L'élément "suivant" de struct node est un pointeur vers un autre struct node , créant ainsi un type de liste.

struct node
{
  int data;           // some integer data
  struct node *next;  // pointer to another struct node
};

Étant donné que la structure de données du nœud struct est définie de manière récursive, les procédures qui l'utilisent peuvent être implémentées naturellement en tant que procédures récursives. La procédure list_print définie ci-dessous parcourt la liste jusqu'à ce que la liste soit vide (c'est-à-dire que le pointeur de liste a une valeur NULL). Pour chaque nœud, il imprime l'élément de données (un entier). Dans l'implémentation C, la liste reste inchangée par la procédure list_print .

void list_print(struct node *list)
{
    if (list != NULL)               // base case
    {
       printf ("%d ", list->data);  // print integer data followed by a space
       list_print (list->next);     // recursive call on the next node
    }
}

Arbres binaires

Vous trouverez ci-dessous une définition simple d'un nœud d'arbre binaire. Comme le nœud des listes chaînées, il est défini en termes de lui-même, de manière récursive. Il existe deux pointeurs auto-référentiels : gauche (pointant vers le sous-arbre gauche) et droit (pointant vers le sous-arbre droit).

struct node
{
  int data;            // some integer data
  struct node *left;   // pointer to the left subtree
  struct node *right;  // point to the right subtree
};

Les opérations sur l'arbre peuvent être implémentées en utilisant la récursivité. Notez qu'étant donné qu'il existe deux pointeurs d'auto-référencement (gauche et droite), les opérations d'arborescence peuvent nécessiter deux appels récursifs :

// Test if tree_node contains i; return 1 if so, 0 if not.
int tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return 0;  // base case
    else if (tree_node->data == i)
        return 1;
    else
        return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);
}

Au plus deux appels récursifs seront effectués pour tout appel donné à tree_contains tel que défini ci-dessus.

// Inorder traversal:
void tree_print(struct node *tree_node) {
    if (tree_node != NULL) {              // base case
        tree_print(tree_node->left);      // go left
        printf("%d ", tree_node->data);   // print the integer followed by a space
        tree_print(tree_node->right);     // go right
    }
}

L'exemple ci-dessus illustre une traversée dans l'ordre de l'arbre binaire. Un arbre de recherche binaire est un cas particulier de l'arbre binaire où les éléments de données de chaque nœud sont en ordre.

Traversée du système de fichiers

Étant donné que le nombre de fichiers dans un système de fichiers peut varier, la récursivité est le seul moyen pratique de parcourir et donc d'énumérer son contenu. La traversée d' un système de fichiers est très similaire à celle de la traversée d'arbre , par conséquent les concepts derrière la traversée d'arbre sont applicables à la traversée d'un système de fichiers. Plus précisément, le code ci-dessous serait un exemple de parcours de pré - ordre d'un système de fichiers.

import java.io.File;

public class FileSystem {

	public static void main(String [] args) {
		traverse();
	}

	/**
	 * Obtains the filesystem roots
	 * Proceeds with the recursive filesystem traversal
	 */
	private static void traverse() {
		File[] fs = File.listRoots();
		for (int i = 0; i < fs.length; i++) {
			System.out.println(fs[i]);
			if (fs[i].isDirectory() && fs[i].canRead()) {
				rtraverse(fs[i]);
			}
		}
	}

	/**
	 * Recursively traverse a given directory
	 *
	 * @param fd indicates the starting point of traversal
	 */
	private static void rtraverse(File fd) {
		File[] fss = fd.listFiles();

		for (int i = 0; i < fss.length; i++) {
			System.out.println(fss[i]);
			if (fss[i].isDirectory() && fss[i].canRead()) {
				rtraverse(fss[i]);
			}
		}
	}

}

Ce code est à la fois récursivité et itération - les fichiers et les répertoires sont itérées, et chaque répertoire est ouvert récursive.

La méthode "rtraverse" est un exemple de récursivité directe, tandis que la méthode "traverse" est une fonction wrapper.

Le scénario du "cas de base" est qu'il y aura toujours un nombre fixe de fichiers et/ou de répertoires dans un système de fichiers donné.

Gain de temps des algorithmes récursifs

L' efficacité temporelle des algorithmes récursifs peut être exprimée dans une relation de récurrence de notation Big O . Ils peuvent (généralement) ensuite être simplifiés en un seul terme Big-O.

Règle de raccourci (théorème maître)

Si la complexité temporelle de la fonction est de la forme

Alors le grand O de la complexité temporelle est donc :

  • Si pour une constante , alors
  • Si , alors
  • Si pour une constante , et si pour une constante c < 1 et tous suffisamment grands n , alors

a représente le nombre d'appels récursifs à chaque niveau de récursivité, b représente de quel facteur plus petit l'entrée est pour le prochain niveau de récursivité (c'est-à-dire le nombre de morceaux en lesquels vous divisez le problème), et f  ( n ) représente le travail la fonction est indépendante de toute récursivité (par exemple, partitionnement, recombinaison) à chaque niveau de récursivité.

Voir également

Remarques

Les références