J'ai un problème pour un laboratoire universitaire;
Écrivez un programme court qui génère toutes les chaînes possibles formées en utilisant des caractères 'C', 'A', 'R', 'B', 'O', et "N" exactement une fois.
Cela semble être une question d'entretien courant et bien documenté.
Je l'ai donc codé avec Java à l'aide d'une méthode récursive qui n'était pas trop difficile, J'ai commencé à coder un compteur qui compterait sur la base 6, la sortie ferait ensuite référence à Char et à imprimer la chaîne.
merci,
6 Réponses :
Oui, il y a beaucoup de fois que je n'utiliserais pas de récursivité. Récursion est pas gratuit, il a un coût dans l'espace de pile et qui peut souvent être une ressource beaucoup plus limitée que d'autres. Il y a aussi un coût temporel, aussi petit, dans la mise en place et la déchirure des cadres de pile. À titre d'exemple, la fonction factorielle beaucoup vantée est celle où je choisirais probablement une approche itérative où les chiffres étaient importants. Calculer 10000! avec (ceci ressemble comme Python, mais c'est seulement parce que Python est une très belle langue pseudo-code): utilisera 10 000 cadres de pile (en supposant Il n'est pas optimisé par le compilateur dans une solution itérative bien sûr), beaucoup. La solution itérative: utilisera juste le cadre d'une pile et précieux petit autre. Il est vrai que les solutions récursives sont souvent plus élégantes, mais vous faut-il tempérer qu'avec les limitations de votre environnement. Votre Par exemple, le code Python suivant fait le truc: produisant: de Bien sûr, si votre chaîne peut être de 10 000 de 10k, je repenserais, car cela impliquerait beaucoup plus de niveaux de pile, mais, à condition de rester suffisamment bas, la récursion est une solution viable. Carbon est un exemple où je voudrais réellement utiliser la récursion depuis:
La récursion de la queue est aussi efficace qu'une version gratuite de récursivité. Et dans ce cas particulier, la récursion est la solution la plus adéquate.
@Nicolas, c'est vrai que si c'est en fait optimisé. La récursion de la queue peut être mais parfois les décisions sur quand recueil sont plus complexes.
Utilisez simplement une boucle et vous éviterez d'utiliser la récursive. La récursion est évitée généralement car elle rend le code moins lisible et plus difficile à maintenir et à déboguer. Si vous avez des ressources basses lorsque Paxdiablo, ledit espace de pile pourrait être précieux pour vous afin d'éviter de l'utiliser.
«La récursion est évitée généralement car elle rend le code moins lisible et plus difficile à maintenir et à déboguer» - cela semble une généralisation plutôt approximative. Avec certains fond mathématiques, des solutions récursives peuvent être assez lisibles. Les approches itératives ont tendance à être une trop centrée sur la machine, qui peut être un peu fastidieuse à lire parfois.
-1 Je ne suis tout simplement pas d'accord avec la première moitié de la réponse, en particulier lorsqu'un tel énoncé audacieux (cette récursion est évitée) n'est pas sauvegardé par une référence de quelque sorte.
En effet, il y a des moments d'utilisation de la récursion et des moments de ne pas être, il faut examiner chaque cas sur ses propres mérites. Souvent, une solution itérative nécessite beaucoup plus de code pour peu de gain.
Lorsqu'il y a beaucoup d'invocations de récursivité, votre pile peut exploser de vous laisser avec Stackoverflowerror. Le bon exemple est le calcul des numéros de Fibonacci (ou problème de Towers Hanoi) avec de base Récursion Vous ne pourrez pas calculer plusieurs de ces chiffres. Que vous pourrez utiliser en utilisant une version non récurrente. Fondamentalement, la récursivité crée une belle solution et c'est une vertu. Vous pouvez toujours avoir une bonne solution de récursion de travail en utilisant Récuission queue
Algorithmes et structures de données de Niklaus Wirth Avoir une section "Quand pas Utiliser Récursion », mais la récursivité est un outil de programmeur utile. Je pense que la compréhension de la récursion est "Doit" pour un programmeur.
Vous avez une approche intelligente de Permutation < / a> problème. Il peut être résolu récursivement (pseudocode):
Comme les personnes ci-dessus ont écrit, la récursivité n'est pas toujours la solution optimale (les appels de fonction peuvent être coûteux et ils consomment la pile à moins que le compilateur puisse optimiser la récursion de la queue). Cependant, il est particulièrement adapté à de tels problèmes que les vôtres.
Bien que théoriquement, il est possible d'exprimer chaque algorithme récursif en termes d'itération (ex. En simulant manuellement la pile d'appel avec une matrice), parfois la solution itérative équivalente est moins élégante. Voici un échantillon:
Utilisez la récursion lorsque vos données sont intrinsèquement hiérarchiques / imbriquées. Utilisez l'itération lorsque vos données sont linéaires / plates.
Dans votre cas, il y a un ordre naturel que vous pouvez imposer aux combinaisons, vous pouvez donc traiter les données comme linéaire, mais si vous le considérez comme un arbre, vous vous retrouvez avec l'approche récursive.
Si la structure de votre algorithme reflète la structure du problème sous-jacent, vous vous retrouvez avec un code plus simple qui est plus facile à comprendre. N'utilisez pas de récursivité simplement parce que votre professeur CS201 pensait que c'était tellement! Cool!
Jamais, jamais, ne jamais utiliser de récursion. ;-)
FYI: Ne supposez pas que la récursion de la queue est optimisée dans la JVM: Stackoverflow.com/Questtions/105834/...
Pour déterminer s'il est approprié d'utiliser la récursion, vous devez vous demander, est-il approprié d'utiliser la récursion?