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

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.

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;
}

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.

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.

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)

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é.

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:] )

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):

• Tours de Hanoi
• Huit reines

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)

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

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

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 ...

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

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.

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

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.

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);

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é.

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.).

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.