Exemples concrets de récursion

Question

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

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

Answer 1

Un exemple concret de récursion

Answer 2

Que diriez-vous de tout ce qui implique une structure de répertoires 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 affiche de manière récursive le contenu d'un répertoire et de ses sous-répertoires.

 import java.io.File;

public class DirectoryContentAnalyserOne implements DirectoryContentAnalyser {

    private static StringBuilder indentation = new StringBuilder();

    public static void main (String args [] ){
        // Here you pass the path to the directory to be scanned
        getDirectoryContent("C:\\DirOne\\DirTwo\\AndSoOn");
    }

    private static void getDirectoryContent(String 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 ( String currentFileOrDirName : currentDirOrFile.list()){
                getPrivateDirectoryContent(currentDirOrFile + "\\" + currentFileOrDirName);
            }

            if (indentation.length() - 3 > 3 ){
                indentation.delete(indentation.length() - 3, indentation.length());
            }
        }       
    }

}
 

Answer 3

Il y a beaucoup de mathy exemples ici, mais vous avez voulu un monde réel exemple, donc, avec un peu de réflexion, c'est peut-être le meilleur que je peux vous offrir:

Vous trouverez une personne qui a contracté une contageous infection, ce qui est non mortelle, et se fixe rapidement( Type A) , à l'Exception de l'une à 5 personnes ( Nous l'appellerons ces type B ) qui deviennent définitivement infecté avec elle et ne montre pas de symptômes et agit simplement d'un épandeur.

Cela crée assez ennuyeux ondes de ravages quand jamais de type B infecte une multitude de type A.

Votre tâche est de traquer tous les type de Bs et de l'immuniser à arrêter l'épine dorsale de la maladie. Malheureusement tho, vous ne pouvez pas administrer l'échelle du pays une cure à tous, parce que les gens qui sont typeAs sont également mortellement allergique à la cure qui fonctionne pour le type B.

La façon dont vous voulez faire cela serait de découverte sociale, étant donné qu'une personne infectée(Type A), choisissez l'ensemble de leurs contacts dans la dernière semaine, le marquage de chaque contact sur un segment. Lorsque vous testez une personne est infectée, les ajouter à la du "suivi" de la file d'attente. Quand une personne est un type B, les ajouter à la "suivre" à la tête ( parce que vous voulez arrêter cette rapide ).

Après le traitement d'une personne donnée, sélectionnez la personne à partir de l'avant de la file d'attente et d'appliquer de la vaccination si nécessaire. Obtenir tous leurs contacts précédemment non visités, et puis testez pour voir si elles sont infectées.

Répétez jusqu'à ce que la file d'attente des personnes infectées devient 0, et puis d'attendre pour un autre foyer..

( Ok, c'est un peu répétitif, mais sa façon itérative de résolution récursive de problème, dans ce cas, la largeur de la première traversée de la population de base en essayant de découvrir probablement chemins de problèmes, et d'ailleurs, itératif, les solutions sont souvent plus efficaces et plus rapides, et je compulsivement supprimer la récursivité partout tellement son devenir instinctif. .... nom d'une pipe! )

Answer 4

Tri rapide , tri par fusion et la plupart des autres tris N-log N.

Answer 5

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