Récursion sans factorielle, nombre de Fibonacci, etc.

48

Presque tous les articles que je trouve sur la récursion incluent les exemples de nombres factoriels ou de Fibonacci, qui sont:

  1. Math
  2. Inutile dans la vraie vie

Existe-t-il des exemples de code non mathématiques intéressants pour enseigner la récursivité?

Je pense aux algorithmes de division et de conquête, mais ils impliquent généralement des structures de données complexes.

lazyCrab
la source
26
Bien que votre question soit tout à fait valide, j’hésiterais à dire que les numéros de Fibonacci sont inutiles dans la vie réelle . Même chose pour factorielle .
Zach L
2
The Little Schemer est un livre entier sur la récursivité qui n'utilise jamais Fact ou Fib. junix-linux-config.googlecode.com/files/…
Eric Wilson
5
@Zach: Malgré tout, la récursivité est un moyen horrible d' implémenter les nombres de Fibonacci, en raison de la durée d'exécution exponentielle.
dan04
2
@ dan04: La récursivité est un moyen horrible d'implémenter presque n'importe quoi à cause de la possibilité de débordement de pile dans la plupart des langues.
R ..
5
@ dan04 à moins que votre langue ne soit assez intelligente pour implémenter l'optimisation d'appels différés comme dans la plupart des langages fonctionnels, auquel cas cela fonctionne très bien
Zachary K

Réponses:

107

Les structures de répertoires / fichiers sont le meilleur exemple d'utilisation de la récursivité, car tout le monde les comprend avant de commencer, mais tout ce qui implique des structures en forme d'arborescence conviendra.

void GetAllFilePaths(Directory dir, List<string> paths)
{
    foreach(File file in dir.Files)
    {
        paths.Add(file.Path);
    }

    foreach(Directory subdir in dir.Directories)
    {
        GetAllFilePaths(subdir, paths)
    }
}

List<string> GetAllFilePaths(Directory dir)
{
    List<string> paths = new List<string>();
    GetAllFilePaths(dir, paths);
    return paths;
}
pdr
la source
1
Merci, je pense que je vais aller avec le système de fichiers. C'est quelque chose de concret et peut être utilisé pour de nombreux exemples du monde réel.
synapse
9
Remarque: la commande unix exclut souvent l'option -r (cp ou rm par exemple). -r signifie récursif.
deadalnix le
7
vous devez être prudent ici car dans le monde réel, les systèmes de fichiers sont en réalité un graphe dirigé, pas nécessairement un arbre, s'ils sont pris en charge par le système de fichiers, les liens physiques, etc. peuvent créer des jointures et des cycles
jk.
1
@jk: les répertoires ne peuvent pas être liés durement, modulez donc quelques feuilles pouvant apparaître à plus d'un endroit, et si vous excluez les liens symboliques, les systèmes de fichiers du monde réel sont des arbres.
R ..
1
il existe d'autres particularités dans certains systèmes de fichiers pour les répertoires, par exemple les points d'analyse NTFS. mon point est que le code qui n'est pas spécifiquement conscient de cela peut avoir des résultats inattendus sur les systèmes de fichiers du monde réel
jk.
51

Recherchez des éléments impliquant des structures arborescentes. Un arbre est relativement facile à saisir et la beauté d'une solution récursive apparaît bien plus tôt qu'avec des structures de données linéaires telles que des listes.

Choses à penser:

  • systèmes de fichiers - ce sont essentiellement des arbres; une bonne tâche de programmation consisterait à récupérer toutes les images .jpg sous un certain répertoire et tous ses sous-répertoires
  • ancêtre - à partir d'un arbre généalogique, trouvez le nombre de générations que vous devez marcher pour trouver un ancêtre commun; ou vérifiez si deux personnes dans l'arbre appartiennent à la même génération; ou vérifiez si deux personnes dans l'arbre peuvent se marier légalement (cela dépend de la juridiction :)
  • Documents de type HTML: convertissez la représentation en série (texte) d'un document en arborescence DOM. effectuer des opérations sur des sous-ensembles d'un DOM (peut-être même implémenter un sous-ensemble de xpath?); ...

Celles-ci sont toutes liées à des scénarios réels et peuvent toutes être utilisées dans des applications d'importance réelle.

tdammers
la source
Bien sûr, il convient de noter que chaque fois que vous avez la liberté de concevoir votre propre arborescence, il est presque toujours préférable de conserver les pointeurs / références vers le parent / le prochain frère / etc. dans les nœuds afin que vous puissiez parcourir l'arborescence sans récursivité.
R ..
1
Qu'est-ce que les pointeurs ont à voir avec ça? Même lorsque vous avez des indications sur le premier enfant, le prochain frère ou le prochain parent, vous devez quand même traverser votre arbre, et dans certains cas, la récursion est la méthode la plus réalisable.
tdammers
41

https://stackoverflow.com/questions/105838/real-world-examples-of-recursion

  • la modélisation d'une infection contagieuse
  • générer de la géométrie
  • gestion de répertoire
  • tri

https://stackoverflow.com/questions/2085834/how-did-you-practically-use-recursion

  • tracé laser
  • échecs
  • analyse du code source (grammaire linguistique)

https://stackoverflow.com/questions/4945128/what-is-a-good-example-of-recursion-other-than-generating-a-fibonacci-sequence

  • Recherche BST
  • Tours de Hanoi
  • recherche palindrome

https://stackoverflow.com/questions/126756/examples-of-recursive-functions

  • Donne une belle histoire en anglais qui illustre la récursion d'une histoire au coucher.
mskfisher
la source
10
Bien que cela puisse théoriquement répondre à la question, il serait préférable d'inclure ici les parties essentielles de ces questions et réponses, et de fournir les liens pour référence. Si les questions sont supprimées de SO, votre réponse sera totalement inutile.
Adam Lear
@Anna Eh bien, les utilisateurs ne peuvent pas supprimer leurs questions, alors quelle est la probabilité que cela se produise?
vemv
4
@vemv Supprimez les votes, les modérateurs, les règles relatives à la modification du sujet ... cela peut arriver. Quoi qu'il en soit, il serait préférable d'avoir une réponse plus complète ici que d'envoyer un visiteur à quatre pages différentes dès le départ.
Adam Lear
@Anna: Dans cet ordre d'idées, toutes les questions fermées en tant que "duplicata exact" devraient avoir la réponse de l'original collée. Cette question est un duplicata exact (des questions sur SO), pourquoi devrait-elle recevoir un traitement différent de celui exact des doublons de questions sur les programmeurs?
SF.
1
@SF Si nous pouvions le fermer en tant que doublon, nous le ferions, mais les doublons entre sites ne sont pas pris en charge. Programmers est un site distinct, de sorte que, dans l’idéal, les réponses fournies ici utiliseraient SO comme toute autre référence et non pas le déléguer entièrement. Ce n'est pas différent de simplement dire "votre réponse est dans ce livre" - techniquement vrai, mais ne peut pas être utilisé immédiatement sans consulter la référence.
Adam Lear
23

Voici quelques problèmes plus pratiques qui me viennent à l’esprit:

  • Tri par fusion
  • Recherche binaire
  • Traversée, insertion et suppression sur des arbres (largement utilisés dans les applications de base de données)
  • Générateur de permutations
  • Sudoku résolveur (avec retour arrière)
  • Vérification orthographique (à nouveau avec retour arrière)
  • Analyse de syntaxe (.eg, un programme qui convertit le préfixe en notation postfixée)
Daniel Scocco
la source
11

QuickSort serait le premier qui saute aux yeux. La recherche binaire est également un problème récursif. Au-delà de cela, il existe des classes entières de problèmes que les solutions retombent presque gratuitement lorsque vous commencez à travailler avec la récursivité.

Zachary K
la source
3
La recherche binaire est souvent formulée comme un problème récursif mais il est trivial (et souvent préférable) de la mettre en œuvre de manière impérative.
moelleux
Selon la langue que vous utilisez, le code peut être ou ne pas être explicitement récursif, impératif ou récursif. Mais il reste un algorithme récursif dans la mesure où vous divisez le problème en morceaux de plus en plus petits pour arriver à la solution.
Zachary K
2
@Zachary: les algorithmes pouvant être implémentés avec la récursion de la queue (comme la recherche binaire) appartiennent à une classe d'espace fondamentalement différente de celles qui nécessitent une vraie récursivité (ou vos propres structures d'état avec des besoins d'espace tout aussi coûteux). Je ne pense pas qu'il soit bénéfique pour eux d'apprendre ensemble, comme s'ils étaient identiques.
R ..
8

Sort, défini récursivement en Python.

def sort( a ):
    if len(a) == 1: return a
    part1= sort( a[:len(a)//2] )
    part2= sort( a[len(a)//2:] )
    return merge( part1, part2 )

Fusionner, défini récursivement.

def merge( a, b ):
    if len(b) == 0: return a
    if len(a) == 0: return b
    if a[0] < b[0]:
        return [ a[0] ] + merge(a[1:], b)
    else:
        return [ b[0] ] + merge(a, b[1:]) 

Recherche linéaire, définie récursivement.

def find( element, sequence ):
    if len(sequence) == 0: return False
    if element == sequence[0]: return True
    return find( element, sequence[1:] )

Recherche binaire, définie récursivement.

def binsearch( element, sequence ):
    if len(sequence) == 0: return False
    mid = len(sequence)//2
    if element < mid: 
        return binsearch( element, sequence[:mid] )
    else:
        return binsearch( element, sequence[mid:] )
S.Lott
la source
6

En un sens, la récursivité consiste à diviser et à conquérir des solutions, c'est-à-dire transformer l'espace du problème en un problème plus petit pour aider à trouver la solution à un problème simple, puis reconstituer le problème initial pour composer la bonne réponse.

Quelques exemples n'impliquant pas les mathématiques pour enseigner la récursion (du moins les problèmes dont je me souviens de mes années universitaires):

Voici des exemples d'utilisation de Backtracking pour résoudre le problème.

Les autres problèmes sont les classiques du domaine de l'intelligence artificielle: utilisation de la recherche approfondie en profondeur, recherche de cheminement, planification.

Tous ces problèmes impliquent une sorte de structure de données "complexe", mais si vous ne voulez pas l'enseigner avec des maths (nombres), vos choix risquent d'être plus limités. Yoy voudra peut-être commencer à enseigner avec une structure de données de base, telle qu'une liste liée. Par exemple, représenter les nombres naturels à l'aide d'une liste:

0 = liste vide 1 = liste avec un noeud. 2 = liste avec 2 nœuds. ...

Définissez ensuite la somme de deux nombres en fonction de cette structure de données, comme suit: Vide + N = N Noeud (X) + N = Noeud (X + N)

Gabriel
la source
5

Tours de Hanoi est un bon pour aider à apprendre la récursion.

Il existe de nombreuses solutions sur le Web dans de nombreuses langues.

Oded
la source
3
C’est en fait à mon avis un autre mauvais exemple. Tout d'abord, c'est irréaliste; ce n'est pas un problème que les gens ont réellement. Deuxièmement, il existe des solutions faciles non-récursives. (L'un est: numérotez les disques. Ne déplacez jamais un disque sur un disque de même parité et n'annulez jamais le dernier mouvement que vous avez effectué. Si vous suivez ces deux règles, vous résolvez le puzzle avec la solution optimale. Aucune récursivité n'est requise. )
Eric Lippert le
5

Un détecteur de palindrome:

Commencez par une chaîne: "ABCDEEDCBA" Si les caractères de début et de fin sont égaux, recursez et cochez "BCDEEDCB", etc ...

NWS
la source
6
C'est également trivial à résoudre sans récursion et, à mon humble avis, mieux résolu sans elle.
Blrfl
3
D'accord, mais OP a spécifiquement demandé des exemples d'enseignement avec une utilisation minimale des structures de données.
NWS
5
Ce n’est pas un bon exemple d’enseignement si vos étudiants peuvent immédiatement penser à une solution non récursive. Pourquoi quelqu'un ferait-il attention alors que votre exemple est "Voici quelque chose de trivial à faire avec une boucle. Maintenant, je vais vous montrer un moyen plus difficile, sans raison apparente."
Réintégrer Monica le
5

Un algorithme de recherche binaire ressemble à ce que vous voulez.

Sardathrion
la source
4

Dans les langages de programmation fonctionnels, lorsqu'aucune fonction d'ordre supérieur n'est disponible, la récursivité est utilisée à la place des boucles impératives afin d'éviter les états mutables.

F # est un langage fonctionnel impur qui autorise les deux styles, donc je vais comparer les deux ici. Le suivant additionne tous les nombres d'une liste.

Boucle impérative avec variable mutable

let xlist = [1;2;3;4;5;6;7;8;9;10]
let mutable sum = 0
for x in xlist do
    sum <- sum + x

Boucle récursive sans état mutable

let xlist = [1;2;3;4;5;6;7;8;9;10]
let rec loop sum xlist = 
    match xlist with
    | [] -> sum
    | x::xlist -> loop (sum + x) xlist
let sum = loop 0 xlist

Notez que ce type d'agrégation est capturé dans la fonction d'ordre supérieur List.foldet pourrait être écrit List.fold (+) 0 xlistou même encore plus simplement avec la fonction de commodité List.sumcomme juste List.sum xlist.

Stephen Swensen
la source
vous mériteriez plus de points que juste +1 de moi. F # sans récursion serait très fastidieux, c'est encore plus vrai pour Haskell qui n'a pas de construction en boucle SEULEMENT la récursivité!
Schoetbi
3

J'ai beaucoup utilisé la récursivité dans le jeu en jouant à l'IA. En écrivant en C ++, j’ai utilisé une série d’environ 7 fonctions qui s’appelaient dans l’ordre (la première fonction ayant la possibilité de contourner toutes ces fonctions et d’appeler à la place une chaîne de 2 fonctions supplémentaires). La dernière fonction de chaque chaîne appelle à nouveau la première fonction jusqu'à ce que la profondeur restante que je voulais rechercher passe à 0. Dans ce cas, la dernière fonction appelle ma fonction d'évaluation et renvoie le score de la position.

Les multiples fonctions me permettaient de créer facilement des branches en fonction des décisions prises par les joueurs ou d’événements aléatoires dans le jeu. Je me servais du passage par référence chaque fois que je le pouvais, car je passais autour de très grandes structures de données, mais à cause de la structure du jeu, il était très difficile d'avoir un "mouvement d'annulation" dans ma recherche, donc J'utiliserais la valeur de passage dans certaines fonctions pour conserver mes données d'origine inchangées. De ce fait, le passage à une approche en boucle plutôt qu’à une approche récursive s’est révélé trop difficile.

Vous pouvez voir un aperçu très basique de ce type de programme, voir https://secure.wikimedia.org/wikipedia/en/wiki/Minimax#Pseudocode

David Stone
la source
3

Un très bon exemple concret dans le monde des affaires est ce qu’on appelle une "nomenclature". Ce sont les données qui représentent tous les composants qui composent un produit fini. Par exemple, utilisons un vélo. Un vélo a un guidon, des roues, un cadre, etc. Chacun de ces composants peut avoir des sous-composants. Par exemple, la roue peut avoir des rayons, une tige de soupape, etc. Ainsi, ils sont généralement représentés dans une arborescence.

Maintenant, pour interroger des informations globales sur la nomenclature ou pour modifier des éléments d'une nomenclature, vous avez souvent recours à la récursivité.

    class BomPart
    {
        public string PartNumber { get; set; }
        public string Desription { get; set; }
        public int Quantity { get; set; }
        public bool Plastic { get; set; }
        public List<BomPart> Components = new List<BomPart>();
    }

Et un exemple d'appel récursif ...

    static int ComponentCount(BomPart part)
    {
        int subCount = 0;
        foreach(BomPart p in part.Components)
            subCount += ComponentCount(p);
        return part.Quantity * Math.Max(1,subCount);

    }

De toute évidence, la classe BomPart aurait beaucoup plus de champs. Vous devrez peut-être déterminer le nombre de composants plastiques dont vous disposez, la quantité de travail nécessaire pour construire une pièce complète, etc. Tout cela nous ramène à l'utilité de la récursivité sur une structure arborescente.

deepee1
la source
Une nomenclature peut être un chemin dirigé plutôt qu'un arbre, par exemple, la même spécification de vis peut être utilisée par plusieurs composants.
Ian
-1

Les relations familiales sont de bons exemples car tout le monde les comprend intuitivement:

ancestor(joe, me) = (joe == me) 
                    OR ancestor(joe, me.father) 
                    OR ancestor(joe, me.mother);
Caleb
la source
Dans quelle langue ce code est-il écrit?
törzsmókus
@ törzsmókus Pas de langue spécifique. La syntaxe est assez proche de C, Obj-C, C ++, Java et de nombreux autres langages, mais si vous voulez du code réel, vous devrez peut-être remplacer un opérateur approprié, tel que ||le OR.
Caleb
-1

Une récursion plutôt inutile mais qui montre bien que la récursivité interne fonctionne bien est la suivante strlen():

size_t strlen( const char* str )
{
    if( *str == 0 ) {
       return 0;
    }
    return 1 + strlen( str + 1 );
}

Pas de maths - une fonction très simple. Bien sûr, vous ne l'implémentez pas de manière récursive dans la vie réelle, mais c'est une bonne démo de la récursivité.

en dents de scie
la source
-2

Un autre problème réel de la récursivité auquel les étudiants peuvent être confrontés consiste à créer leur propre robot d'exploration Web qui extrait les informations d'un site Web et suit tous les liens de ce site (et tous les liens de ces liens, etc.).

GregW
la source
2
C'est généralement mieux servi par une file d'attente de processus que par la récursivité au sens traditionnel.
moelleux
-2

J'ai résolu un problème avec un motif de chevalier (sur un échiquier) en utilisant un programme récursif. Vous étiez censé déplacer le chevalier pour qu'il touche toutes les cases sauf quelques cases marquées.

Vous simplement:

mark your "Current" square
gather a list of free squares that are valid moves
are there no valid moves?
    are all squares marked?
        you win!
for each free square
    recurse!
clear the mark on your current square.
return.    

De nombreux types de scénarios "anticipés" peuvent être élaborés en testant les possibilités futures dans un arbre comme celui-ci.

Bill K
la source