Y a-t-il des exemples de récursivité en utilisant uniquement la zone de tas?
6 Réponses :
in c, la récursion basée sur l'appel de fonction utilise toujours la pile, presque par définition.
Si vous êtes prêt à convertir votre récursion en itération, il est possible d'utiliser uniquement des espaces de tas, mais ce n'est pas vraiment une récursion. Vous le feriez en mettant en œuvre une pile dans le tas.
Certains problèmes peuvent utiliser Récursion queue , qui écrase à plusieurs reprises la même zone de la pile.
Vous pouvez avoir une méthode hybride. La pile d'appels est toujours utilisée pour des paramètres simples et des adresses de retour, mais les grands paramètres tels que des tableaux et des couplettes sont conservés dans une pile allouée en tas. Vous pouvez donc atteindre une récursion (relativement) profonde sans exploser la pile (appel) TI rapidement.
Pas toujours correct; Vous pouvez faire un peu de piratage pour déplacer le pointeur de pile sur le tas pour une récursion très de dueep: Gist.github .COM / MSG555 / 5418199
Vous pouvez faire quelque chose de fou comme Malloc une nouvelle zone, désactiver les interruptions et à peu près tout (pas possible sur de nombreux systèmes) et définissez votre pointeur de pile sur cette zone Malloc. Vous jouez techniquement avec une pile, mais cet emplacement de pile est maintenant sur le tas. Pas une bonne idée de le faire, mais cela peut fonctionner sur certains systèmes de type intégrés où vous avez ce niveau de contrôle.
Je ne suis pas sûr que j'achète cela élimine la pile, mais +1 pour la créativité.
J'ai utilisé cela sur la paume pour mettre en œuvre un jeu AI avec une récursion profonde.
Dans de nombreuses implémentations, les arguments à un appel de fonction sont stockés sur la pile. Des informations telles que l'adresse à revenir peuvent également être stockées sur la pile. Ainsi, avoir une fonction récursive sans utiliser la pile peut ne pas être réalisable.
Vérifiez votre documentation de compilateur pour voir si une fonction peut être appelée sans utiliser de place sur la pile. Si oui, vous êtes sur votre chemin.
Pour que la fonction soit récursive, elle doit s'appeler au moins une fois. Quand il s'appelle lui-même, il place un pointeur sur la pile pour le retour de l'appel récursif. La pile, bien sûr, n'est pas le tas, et donc une fonction récursive qui utilise uniquement le tas n'est pas possible.
(au moins, pas dans C. Les langues fonctionnelles sont optimisées pour réutiliser l'espace de pile et ne pas allouer des pointeurs pour les appels de retour)
Oui, il est possible de mettre en œuvre la récursion en utilisant uniquement le tas, et dans certains cas, il est très souhaitable. Par exemple, voir python sans empilement . L'un des principaux avantages de ceci est qu'un thread entier peut devenir sérialisable et vous pouvez littéralement expédier un fil d'un hôte à un autre (même d'un autre système d'architecture et d'exploitation!).
Je le fais de cette façon:
Alors ...
Habituellement, je l'implique comme une classe d'utilité "Recursor" Objets implémenter l'interface "irecursable"
La classe de la récursure peut être invitée à recueillir la profondeur-première ou la largeur - première.
Ma mise en œuvre appelle également la récursionbegine () et la récursivité () sur le nœud racine, de sorte que la classe en cours de recouvre peut gérer tout code d'initialisation et de nettoyage requis.
La classe recueillie peut également avoir la racine notifiée de chaque pair appelée - lui permettant de voir:
Récursionbegin () - appelé une fois, avant le début de la récursivité. Ces méthodes font partie de l'interface irecurse et peuvent être remplacées pour permettre à la classe d'être flexible dans la manière dont il utilise le chien de recuisson.
Parfois, je déplace ces utilitaires en une seule classe appelée recursable qui combine les caractéristiques du récursoir de classe et de l'interface irecurse ... ou de les combiner pleinement dans la classe d'objet, ce qui signifie que la classe à recouverte devient auto-recouvrable, sans aucun besoin de soutien classes.
espérons que cela aide quelqu'un à faire un démarrage sur la conversion d'algorithmes récursifs aux algorithmes à base de tas ... et évitez de clocer la pile ou de causer de mauvais empilements de pile
tbh, la récursion est diabolique et doit être évité comme la peste! (sauf où votre langue permet une vraie récursive de la queue de queue)
... respectez la pile, c'est une ressource précieuse !!!
RécursionElement () - appelé plusieurs fois (facultatif).
Recursionend () - appelé une fois, après la fin de la récursion.
Ce n'est pas une question de devoirs, n'est-ce pas?
@gcc pas besoin de faire défensif ... Cela ressemble à une question typique des devoirs, et si c'est le cas, je préférerais ne pas y répondre directement. Si ce n'est pas le cas, il n'y a pas de problème.
Des questions qui ne mentionnent pas pourquoi vous avez besoin d'eux sont souvent des questions de devoirs. Tout OP devrait être correct avec les gens qui souhaitent s'assurer qu'ils ne font pas les devoirs de quelqu'un d'autre.