Exemples réels de récursivité

Quels sont les problèmes réels où une approche récursive est la solution naturelle en dehors de la recherche en profondeur (DFS)?

(Je ne considère pas Tower of Hanoi , le nombre de Fibonacci ou les problèmes factoriels du monde réel. Ils sont un peu artificiels dans mon esprit.)

Il y a beaucoup d’exemples de mathématiques ici, mais vous vouliez un exemple du monde réel , donc avec un peu de reflection, c’est probablement le meilleur que je puisse offrir:

Vous trouvez une personne qui a contracté une infection contagieuse donnée, qui n’est pas fatale, et qui se fixe rapidement (type A), sauf une personne sur cinq (nous appellerons ces personnes de type B) qui devient infectée de façon permanente et ne montre pas symptômes et agit simplement comme un épandeur.

Cela crée des vagues de dégâts assez ennuyeuses quand le type B infecte une multitude de types A.

Votre tâche est de retrouver tous les types B et de les immuniser pour arrêter l’épine dorsale de la maladie. Malheureusement, vous ne pouvez pas administrer un remède national à tous, car les personnes qui sont de type sont également mortellement allergiques au traitement qui fonctionne pour le type B.

La façon dont vous le feriez serait une découverte sociale, étant donné une personne infectée (Type A), choisissez tous ses contacts au cours de la dernière semaine, marquant chaque contact sur un tas. Lorsque vous testez une personne infectée, ajoutez-la à la queue de suivi. Quand une personne est un type B, ajoutez-les au “suivi” à la tête (parce que vous voulez arrêter ce jeûne).

Après avoir traité une personne donnée, sélectionnez-la en tête de liste et appliquez-la si nécessaire. Obtenez tous leurs contacts précédemment non visités, puis testez pour voir s’ils sont infectés.

Répétez jusqu’à ce que la queue des personnes infectées devienne égale à 0, puis attendez une autre épidémie.

(Ok, c’est un peu itératif, mais c’est une façon itérative de résoudre un problème récursif, dans ce cas, une première traversée d’une population essayant de découvrir des chemins probables vers des problèmes, et les solutions itératives sont souvent plus rapides et efficaces) , et je supprime obligatoirement la récursion partout où elle est devenue instinctive.

Un exemple concret de récursivité

Un tournesol

Que diriez-vous de tout ce qui implique une structure de répertoire dans le système de fichiers. Recherche récursive de fichiers, suppression de fichiers, création de répertoires, etc.

Voici une implémentation Java qui imprime récursivement le contenu d’un répertoire et de ses sous-répertoires.

import java.io.File; public class DirectoryContentAnalyserOne implements DirectoryContentAnalyser { private static SsortingngBuilder indentation = new SsortingngBuilder(); public static void main (Ssortingng args [] ){ // Here you pass the path to the directory to be scanned getDirectoryContent("C:\\DirOne\\DirTwo\\AndSoOn"); } private static void getDirectoryContent(Ssortingng filePath) { File currentDirOrFile = new File(filePath); if ( !currentDirOrFile.exists() ){ return; } else if ( currentDirOrFile.isFile() ){ System.out.println(indentation + currentDirOrFile.getName()); return; } else{ System.out.println("\n" + indentation + "|_" +currentDirOrFile.getName()); indentation.append(" "); for ( Ssortingng currentFileOrDirName : currentDirOrFile.list()){ getPrivateDirectoryContent(currentDirOrFile + "\\" + currentFileOrDirName); } if (indentation.length() - 3 > 3 ){ indentation.delete(indentation.length() - 3, indentation.length()); } } } } 

Tri rapide , sorting par fusion et la plupart des autres sortings N-log N.

L’exemple de Matt Dillard est bon. Plus généralement, toute marche d’un arbre peut généralement être traitée par récursivité très facilement. Par exemple, comstackr des arbres d’parsing, marcher sur XML ou HTML, etc.

La récursivité est souvent utilisée dans les implémentations de l’ algorithme Backtracking . Pour une application “réelle”, que diriez-vous d’un solveur Sudoku ?

La récursivité est appropriée lorsqu’un problème peut être résolu en le divisant en sous-problèmes, qui peuvent utiliser le même algorithme pour les résoudre. Les algorithmes sur les arbres et les listes sortingées sont un ajustement naturel. De nombreux problèmes de géomésortinge informatique (et de jeux 3D) peuvent être résolus de manière récursive en utilisant des arborescences de partitionnement d’espace binary (BSP), des subdivisions de graisses ou d’autres moyens de diviser le monde en sous-parties.

La récursivité est également appropriée lorsque vous essayez de garantir l’exactitude d’un algorithme. Étant donné une fonction qui prend des entrées immuables et renvoie un résultat qui est une combinaison d’appels récursifs et non récursifs sur les entrées, il est généralement facile de prouver que la fonction est correcte (ou non) en utilisant une induction mathématique. Il est souvent impossible de le faire avec une fonction itérative ou avec des entrées susceptibles de muter. Cela peut être utile lorsque vous traitez des calculs financiers et d’autres applications où l’exactitude est très importante.

Sûrement que beaucoup de compilateurs là-bas utilisent beaucoup la récursivité. Les langages informatiques sont eux-mêmes récursifs de manière inhérente (c.-à-d. Que vous pouvez incorporer des instructions if dans d’autres déclarations if, etc.).

Désactiver / définir en lecture seule pour tous les contrôles enfants dans un contrôle de conteneur. Je devais le faire parce que certains des contrôles d’enfants étaient des conteneurs eux-mêmes.

 public static void SetReadOnly(Control ctrl, bool readOnly) { //set the control read only SetControlReadOnly(ctrl, readOnly); if (ctrl.Controls != null && ctrl.Controls.Count > 0) { //recursively loop through all child controls foreach (Control c in ctrl.Controls) SetReadOnly(c, readOnly); } } 

Eval / Apply cycle célèbre de SICP

texte alt

Voici la définition de eval:

 (define (eval exp env) (cond ((self-evaluating? exp) exp) ((variable? exp) (lookup-variable-value exp env)) ((quoted? exp) (text-of-quotation exp)) ((assignment? exp) (eval-assignment exp env)) ((definition? exp) (eval-definition exp env)) ((if? exp) (eval-if exp env)) ((lambda? exp) (make-procedure (lambda-parameters exp) (lambda-body exp) env)) ((begin? exp) (eval-sequence (begin-actions exp) env)) ((cond? exp) (eval (cond->if exp) env)) ((application? exp) (apply (eval (operator exp) env) (list-of-values (operands exp) env))) (else (error "Unknown expression type - EVAL" exp)))) 

Voici la définition de appliquer:

 (define (apply procedure arguments) (cond ((primitive-procedure? procedure) (apply-primitive-procedure procedure arguments)) ((compound-procedure? procedure) (eval-sequence (procedure-body procedure) (extend-environment (procedure-parameters procedure) arguments (procedure-environment procedure)))) (else (error "Unknown procedure type - APPLY" procedure)))) 

Voici la définition de eval-sequence:

 (define (eval-sequence exps env) (cond ((last-exp? exps) (eval (first-exp exps) env)) (else (eval (first-exp exps) env) (eval-sequence (rest-exps exps) env)))) 

eval -> apply -> eval-sequence -> eval

La récursivité est utilisée dans des domaines tels que les arbres BSP pour la détection des collisions dans le développement de jeux (et dans d’autres domaines similaires).

Les gens sortingent souvent des stacks de documents en utilisant une méthode récursive. Par exemple, imaginez que vous sortingez 100 documents avec des noms. Commencez par placer les documents dans la stack par la première lettre, puis sortingez chaque stack.

La recherche de mots dans le dictionnaire est souvent effectuée par une technique de type recherche binary, qui est récursive.

Dans les organisations, les chefs donnent souvent des commandes aux chefs de département, qui à leur tour donnent des commandes aux responsables, etc.

Les parsingurs et compilateurs peuvent être écrits selon une méthode de descente récursive. Ce n’est pas la meilleure façon de le faire, car les outils comme lex / yacc génèrent des parsingurs plus rapides et plus efficaces, mais conceptuellement simples et faciles à mettre en œuvre, de sorte qu’ils restnt communs.

Exigence du monde réel je me suis récemment:

Exigence A: implémentez cette fonctionnalité après avoir bien compris l’exigence A.

La récursivité est appliquée aux problèmes (situations) où vous pouvez diviser (réduire le) en parties plus petites, et chaque partie ressemble au problème d’origine.

Les bons exemples de choses qui contiennent des parties plus petites similaires à elle-même sont:

  • arborescence (une twig est comme un arbre)
  • listes (une partie d’une liste est encore une liste)
  • conteneurs (poupées russes)
  • séquences (une partie d’une séquence ressemble à la suivante)
  • groupes d’objects (un sous-groupe est un groupe d’objects)

La récursivité est une technique qui permet de diviser le problème en parties de plus en plus petites, jusqu’à ce que l’une de ces pièces devienne suffisamment petite pour devenir un morceau de gâteau. Bien sûr, après les avoir séparés, vous devez “assembler” les résultats dans le bon ordre pour former une solution totale à votre problème initial.

Certains algorithmes de sorting récursifs, algorithmes de parcours d’arbres, algorithmes de cartographie / réduction, diviser-pour-conquérir sont tous des exemples de cette technique.

En programmation informatique, la plupart des langages de type retour d’appel basés sur des stacks ont déjà les capacités intégrées pour la récursivité:

  • décomposer le problème en parties plus petites ==> s’appeler sur un sous-ensemble plus petit des données d’origine),
  • garder la trace de la façon dont les pièces sont divisées ==> stack d’appel,
  • recoudre les résultats ==> retour par stack

J’ai un système qui utilise la récursivité pure dans quelques endroits pour simuler une machine à états.

Quelques excellents exemples de récursivité se trouvent dans les langages de programmation fonctionnels . Dans les langages de programmation fonctionnels ( Erlang , Haskell , ML / OCaml / F # , etc.), il est très courant de recourir à la récursivité pour le traitement des listes.

Lorsque vous traitez des listes dans des langages de type OOP impératifs typiques, il est très courant de voir des listes implémentées comme des listes liées ([item1 -> item2 -> item3 -> item4]). Cependant, dans certains langages de programmation fonctionnels, vous trouvez que les listes elles-mêmes sont implémentées de manière récursive, où la “tête” de la liste pointe vers le premier élément de la liste et la “queue” pointe vers une liste contenant le rest des éléments ( [item1 -> [item2 -> [item3 -> [item4 -> []]]]]). C’est assez créatif à mon avis.

Cette gestion des listes, lorsqu’elle est associée à une correspondance de modèle, est TRÈS puissante. Disons que je veux additionner une liste de nombres:

 let rec Sum numbers = match numbers with | [] -> 0 | head::tail -> head + Sum tail 

Ceci dit essentiellement “si on nous appelait avec une liste vide, retourne 0” (ce qui nous permet de rompre la récursivité), sinon retourne la valeur de head + la valeur de Sum appelée avec les éléments restants (notre récursivité).

Par exemple, je pourrais avoir une liste d’ URL , je pense que séparer toutes les URL auxquelles chaque URL est liée, puis réduire le nombre total de liens vers / de toutes les URL pour générer des “valeurs” pour une page prend avec PageRank et que vous pouvez trouver défini dans le papier MapReduce original). Vous pouvez le faire pour générer des comptes de mots dans un document également. Et beaucoup, beaucoup, beaucoup d’autres choses aussi.

Vous pouvez étendre ce modèle fonctionnel à tout type de code MapReduce où vous pouvez prendre une liste de quelque chose, la transformer et renvoyer quelque chose (que ce soit une autre liste ou une commande zip sur la liste).

XML, ou parcourant tout ce qui est un arbre. Bien que, pour être honnête, je n’utilise pratiquement jamais la récursivité dans mon travail.

Boucles de rétroaction dans une organisation hiérarchique.

Le chef supérieur demande aux frameworks supérieurs de recueillir les commentaires de tous les membres de l’entreprise.

Chaque exécutif rassemble ses rapports directs et leur demande de recueillir les commentaires de leurs rapports directs.

Et sur la ligne.

Les personnes sans rapport direct – les nœuds de la feuille dans l’arbre – donnent leur avis.

La rétroaction sauvegarde l’arborescence, chaque gestionnaire ajoutant ses propres commentaires.

Finalement, tous les commentaires le font revenir au meilleur patron.

C’est la solution naturelle car la méthode récursive permet de filtrer à chaque niveau – le regroupement des doublons et la suppression des retours offensants. Le chef supérieur peut envoyer un e-mail global et demander à chaque employé de lui faire part directement de ses commentaires, mais il y a les problèmes “vous ne pouvez pas gérer la vérité” et “vous êtes viré”.

Supposons que vous construisiez un CMS pour un site Web, où vos pages se trouvent dans une arborescence, par exemple la racine étant la page d’accueil.

Supposons également que votre {utilisateur | client | client | patron} vous demande de placer un fil d’Ariane sur chaque page pour indiquer où vous vous trouvez dans l’arborescence.

Pour toute page donnée n, vous souhaiterez peut-être accéder au parent de n et à son parent, et ainsi de suite, pour créer une liste de noeuds à la racine de l’arborescence.

Bien sûr, vous frappez la firebase database plusieurs fois par page dans cet exemple, vous pouvez donc utiliser un alias SQL où vous recherchez la table de pages en tant que, et la table de page à nouveau en tant que b, et rejoignez a.id avec b.parent pour que la firebase database fasse les jointures récursives. Cela fait longtemps que ma syntaxe n’est probablement pas utile.

Là encore, vous pouvez simplement calculer cette valeur et la stocker avec l’enregistrement de la page, en ne la mettant à jour que si vous déplacez la page. Ce serait probablement plus efficace.

En tout cas, c’est mon $ .02

Vous avez un organigramme de niveaux N profond. Plusieurs des nœuds sont vérifiés et vous souhaitez étendre uniquement les nœuds vérifiés.

C’est quelque chose que j’ai réellement codé. C’est agréable et facile avec la récursivité.

Dans mon travail, nous avons un système avec une structure de données générique qui peut être décrite comme un arbre. Cela signifie que la récursivité est une technique très efficace pour travailler avec les données.

Le résoudre sans récursivité nécessiterait beaucoup de code inutile. Le problème avec la récursivité est qu’il n’est pas facile de suivre ce qui se passe. Vous devez vraiment vous concentrer lorsque vous suivez le stream d’exécution. Mais quand cela fonctionne, le code est élégant et efficace.

Calculs pour la finance / physique, tels que les moyennes composées.

  • Analyse d’un fichier XML .
  • Recherche efficace dans des espaces multidimensionnels. Par exemple. quad-arbres en 2D, oct-arbres en 3D, kd-arbres, etc.
  • Classification hiérarchique.
  • En y pensant, traverser n’importe quelle structure hiérarchique se prête naturellement à la récursivité.
  • Métaprogrammation des templates en C ++, où il n’y a pas de boucles et la récursivité est la seule solution.

Analyse d’une arborescence de contrôles dans Windows Forms ou WebForms (.NET Windows Forms / ASP.NET ).

Le meilleur exemple que je connaisse est la rapidité , c’est beaucoup plus simple avec la récursivité. Jeter un coup d’œil à:

shop.oreilly.com/product/9780596510046.do

http://www.amazon.com/Beautiful-Code-Leading-Programmers-Practice/dp/0596510047

(Cliquez sur le premier sous-titre du chapitre 3: “Le plus beau code que j’ai écrit”).

Les entresockets de téléphonie et de câblodissortingbution maintiennent un modèle de leur topologie de câblage, qui est en fait un réseau ou un graphique volumineux. La récursivité est un moyen de parcourir ce modèle lorsque vous souhaitez rechercher tous les éléments parents ou tous les éléments enfants.

Étant donné que la récursivité est coûteuse du sharepoint vue du traitement et de la mémoire, cette étape est généralement effectuée uniquement lorsque la topologie est modifiée et que le résultat est stocké dans un format de liste pré-ordonné modifié.

Le raisonnement inductif, processus de formation de concept, est de nature récursive. Votre cerveau le fait tout le temps, dans le monde réel.

Idem le commentaire sur les compilateurs. Les nœuds d’arbre de syntaxe abstraite se prêtent naturellement à la récursivité. Toutes les structures de données récursives (listes liées, arborescences, graphiques, etc.) sont également plus faciles à gérer avec la récursivité. Je pense que la plupart d’entre nous n’ont pas beaucoup recours à la récursivité une fois que nous ne sums plus à l’école à cause du type de problèmes réels, mais il est bon d’en être conscient.

La multiplication des nombres naturels est un exemple réel de récursivité:

 To multiply x by y if x is 0 the answer is 0 if x is 1 the answer is y otherwise multiply x - 1 by y, and add x