La récursivité - comme nous le savons tous - est l'un de ces problèmes - qui vous entoure la tête ressemble à un «jalon» dans votre voyage de programmation.
Mais quand il s'agit de l'utiliser réellement dans des problèmes du monde réel - connaître la mécanique de la récursivité ne suffit pas - il faut également comprendre la nature des problèmes où la récursivité est la solution la plus appropriée.
Voici donc ma question...
- quels sont les "schémas de problèmes" qui appellent la solution de la récursivité
- la récursivité est-elle une forme de stratégie "diviser et conquérir" ou une forme de "réutilisation de code" - ou, est un modèle de conception à part entière
- pouvez-vous nous donner un exemple d'un problème du monde réel où la récursivité vient à l'esprit comme une solution immédiate
-- METTRE À JOUR --
beaucoup de réponses se réfèrent à de "vrais problèmes" comme la traversée d'arbres, de factorielle, etc. Je préférerais "les VRAIS vrais problèmes" - laissez-moi vous donner un exemple ...
Nous avions un GRAND groupe de texte (environ 30 Mo de texte sous forme de liste liée structs), et nous devions en faire un index pour la recherche en texte intégral. Nous devions garder l'index entier en mémoire et réindexer le texte toutes les 10 minutes.
Toutes les 10 minutes, nous comparions le texte entier (deux listes liées, ligne par ligne) avec un morceau de texte nouvellement généré - pour voir quelle ligne a été modifiée - puis nous ré-indexions uniquement cette ligne - de cette façon nous pourrions éviter d'avoir à réindexer le texte ENTIER. N'oubliez pas - nous devions trouver les points de diff entre deux listes liées de 30 Mo.
Un de mes collègues a mis au point un programme fantastique qui utilisait la récursivité LOURDE pour comparer les lignes - puis collecter les positions où les mandrins différaient dans un tableau - oui je sais que cela semble déroutant - comment la récursivité pourrait aider ici - mais ça faisait.
Le point est - comment pourrait-il voir que ce problème pourrait être résolu intelligemment avec une utilisation intensive de la récursivité?
Réponses:
Je ne dirais pas qu'il existe une telle chose comme un modèle de problème pour l'utilisation de la récursivité. Chaque fonction qui peut être implémentée avec la récursivité peut également être implémentée de manière itérative, souvent en poussant et en éclatant une pile.
C'est une question d'expression mais aussi de performance. Les algorithmes itératifs ont souvent de meilleures performances et sont plus faciles à optimiser. Cependant, les algorithmes récursifs bénéficient d'une expression plus claire et sont donc souvent plus faciles à lire, à comprendre et à mettre en œuvre.
Certaines choses ne peuvent même pas être exprimées sans récursivité, des listes infinies par exemple. Les soi-disant langages fonctionnels s'appuient fortement sur la récursivité, car c'est leur mode d'expression naturel. Le dicton est: "La programmation récursive est une programmation fonctionnelle bien faite".
Je n'appellerais pas cela un modèle de conception. C'est une question d'expression. Parfois, une expression récursive est simplement plus puissante et plus expressive et conduit ainsi à un code meilleur et plus propre.
Tout ce qui doit traverser les arbres sera correctement exprimé par un algorithme récursif.
la source
Ni. Divide & conquer utilise la récursivité. Mais la récursivité n'est pas nécessairement diviser pour mieux régner puisque cette dernière signifie diviser un problème en deux (ou plus) parties et résoudre chacune de celles-ci de manière symétrique. En récursivité, vous ne faites pas cela.
La réutilisation du code est complètement indépendante et un modèle de conception entre en jeu à un niveau beaucoup plus élevé. Par exemple, même diviser et conquérir (également un modèle de niveau supérieur à la récursivité) n'est toujours pas considéré comme un modèle de conception - c'est plutôt un modèle algorithmique .
Traversée des arbres. Ou plus généralement la traversée de graphe. Cela comprend notamment la traversée d'une structure de dossiers.
Et bien sûr, tout ce qui utilise la division et la conquête ou la programmation dynamique, car les deux sont naturellement exprimés en termes de récursivité.
la source
Dérivé de l'auto-similitude des fractales, je dirais que l'auto-égalité ou l'identité de soi (ou comment on l'appelle) est un modèle de problème typique pour la récursivité. C'est-à-dire qu'un problème peut être divisé en sous-problèmes qui ont la même structure que le problème principal.
Dans l'arborescence mentionnée, chaque sous-arbre est un arbre complet en lui-même, tout comme l'arbre principal, et l'arbre principal peut être un sous-arbre dans un autre arbre.
Je suppose donc que votre collègue a découvert les propriétés d'auto-égalité de votre problème d'indexation. Ou bien il a fait l'inverse et a transformé le problème en une représentation à égalité de soi.
la source
Eh bien, la récursivité peut être facilement comprise si l'on essaie de transformer des boucles impératives en fonctions fonctionnelles. Quoi qu'il en soit, essayons de donner des réponses à toutes les questions:
Si vous avez une structure ou un algorithme en forme d'arbre, vous aurez besoin d'une récursivité. Si votre code impératif concerne une pile, vous aurez besoin d'une récursivité. Si une certaine étape de votre algorithme dépend des étapes précédentes (boucles de réflexion), vous avez besoin d'une récursivité. Le besoin ici doit être interprété comme peut être utilisé.
Aucun. Diviser pour régner utilise la récursivité mais peut être implémenté avec des piles. La réutilisation du code fait référence à autre chose. Les modèles de conception sont plus compliqués qu'une simple récursivité.
Analyse et tout ce qui concerne les structures arborescentes. Même des structures arborescentes implicites.
la source
S'il existe un moyen de le simplifier pour qu'il soit facile, cela peut être l'indice que la récursivité pourrait fonctionner. Vous pouvez prendre le tri et la recherche d'exemples où il existe des solutions récursives telles que Merge Sort et Binary Search respectivement.
Il faut garder à l'esprit comment certains problèmes peuvent être mal résolus avec la récursion comme une factorielle.
En ce qui concerne un exemple du monde réel où j'utiliserais la récursivité, la recherche d'un livre sur une étagère peut être effectuée assez facilement de manière récursive. Je regarde simplement le livre et si ce n'est pas ce que je veux, je passe au suivant. Je m'arrête lorsque je trouve le livre ou que je touche la fin de la ligne. La boucle sur la vérification d'un livre et le passage au suivant pourrait se faire récursivement. C'est peut-être un exemple trop réel.
la source
En termes très généraux, la récursivité est nécessaire lorsque vous résolvez un problème où f (x) = f (g (x)) . Sauf si vous êtes d'accord avec la récursion infinie, g (x) ne devrait pas être évalué à x .
Aucune de ces réponses. C'est juste une façon de répéter la même chose, parfois en fonction des variations de l'entrée. Le concept existe depuis bien plus longtemps que les modèles de conception, la réutilisation de code ou même les ordinateurs, d'ailleurs.
Les factorielles, la séquence de Fibonacci, la traversée des arbres et bien d'autres problèmes peuvent être résolus avec la récusation. La récursivité dans le sens d'une fonction s'appelant elle-même n'est pas nécessairement la meilleure façon d'implémenter ce genre de choses; il existe d'autres façons d'obtenir le même effet (par exemple, une pile et une boucle) qui pourraient être plus souhaitables.
la source
Lorsque vous écrivez un algorithme récursif, vous traduisez généralement une définition récursive du problème dans le code. Ensuite, vous n'avez même pas besoin de savoir comment il sera exécuté.
C'est ce qui se passe dans la programmation fonctionnelle. En fait, vous spécifiez quoi (définition) plutôt que comment . En d'autres termes, vous définissez la base puis définissez votre problème dans le terme d'un sous-problème.
Par exemple, considérez l'
FactorialalgorithmeEnsuite, lorsque vous rencontrez un problème, vous devriez penser si vous pouvez le définir récursivement ou non, si vous pouvez le définir récursivement, vous l'avez presque résolu.
Cependant, toute fonction récursive ne doit pas être une définition récursive. Vous pouvez définir la base et relier (définir) la solution du problème principal à la solution (définition) des sous-problèmes. Mais pour cette relation, vous aurez peut-être besoin d'une procédure.
Un exemple est
MergeSortdans lequelmergepourrait être une procédure impérative pour relier la définition ou la solution de tri du tableau entier au tri des sous-tableaux.la source