Gegeben die folgende Definition für einen (nicht binären) Baum:
%Vor%Ich habe die folgende Methode fold geschrieben:
%Vor%das kann unter anderem für diese map Methode verwendet werden:
%Vor%Frage: Kann mir jemand helfen, wie man eine tail rekursive Version der obigen fold schreibt?
Ich glaube, Sie brauchen einen Stack, um eine solche Traversierung durchzuführen, genau wie bei der imperativen Programmierung, würde es keinen natürlichen Weg geben, das ohne eine rekursive Methode zu schreiben. Natürlich können Sie den Stack immer selbst verwalten, wodurch er in den Heap verschoben wird und Stack-Überläufe verhindert werden. Hier ist ein Beispiel:
%Vor% Hinweis: Ich habe Node covariant gemacht, nicht unbedingt notwendig, aber wenn dies nicht der Fall ist, müssen Sie an einigen Stellen explizit den Typ von ein paar Nil (z. B. ersetzen durch List[X]() ) angeben.
go es ist eindeutig rekursiv, aber nur weil es den Stack selbst verwaltet.
Sie finden vielleicht eine eher prinzipielle und systematische Technik (aber nicht leicht zu verstehen), basierend auf Fortsetzungen und Trampolinen, in diesen netten Blogpost .
Tags und Links scala tree tail-recursion