Behalten der Stapelposition einer rekursiven Funktion zwischen Aufrufen

Question

Diese Frage ist allgemein, aber ich denke, dass es am besten mit einem bestimmten Beispiel erklärt wird. Nehmen wir an, ich habe ein Verzeichnis mit vielen verschachtelten Unterverzeichnissen und in einigen dieser Unterverzeichnisse gibt es Textdateien, die mit ".txt" enden. Eine Probe Struktur könnte sein:

dir1 
    dir2 
     file1.txt 
    dir3 
     file2.txt 
    file3.txt 

ich interessieren würde, wenn es eine Möglichkeit, in Java ist, ein Verfahren zu entwickeln, die die aufeinanderfolgenden Textdateien bezeichnet werden könnten zurückkehren:

TextCrawler crawler = new TextCrawler(new File("dir1")); 
File textFile; 
textFile = crawler.nextFile(); // value is file1.txt 
textFile = crawler.nextFile(); // value is file2.txt 
textFile = crawler.nextFile(); // value is file3.txt 

Hier Die Herausforderung: Keine interne Liste aller Textdateien kann im Crawler-Objekt gespeichert werden. Das ist trivial. In diesem Fall würden Sie einfach in die Initialisierung eine Methode einbauen, die rekursiv die Liste der Dateien erstellt.

Gibt es einen allgemeinen Weg pausiert eine rekursive Methode, so dass, wenn es erneut aufgerufen wird, es zu dem bestimmten Punkt im Stapel zurückkehrt, wo es übrig? Oder müssen wir etwas schreiben, das für jede Situation spezifisch ist und die Lösungen notwendigerweise für Datei-Crawler, Organigramm-Suchen, rekursive Prime-Finder usw. variieren müssen?

Answer 1

Wenn Sie eine Lösung wünschen, die mit jeder rekursiven Funktion funktioniert, können Sie ein Objekt Consumer akzeptieren. Es kann wie folgt aussehen:

public void recursiveMethod(Consumer<TreeNode> func, TreeNode node){ 
    if(node.isLeafNode()){ 
     func.accept(node); 
    } else{ 
    //Perform recursive call 
    } 
} 

Für eine Reihe von Dateien, es könnte wie folgt aussehen:

public void recursiveMethod(Consumer<File> func, File curFile){ 
    if(curFile.isFile()){ 
     func.accept(curFile); 
    } else{ 
    for(File f : curFile.listFiles()){ 
     recursiveMethod(func, f); 
    } 
    } 
} 

Sie können es dann rufen Sie mit:

File startingFile; 
//Initialize f as pointing to a directory 
recursiveMethod((File file)->{ 
    //Do something with file 
}, startingFile); 

Passen Sie nach Bedarf .

Answer 2

Ich denke, der Zustand sollte gespeichert werden, während Sie von Ihrer rekursiven Funktion zurückkehren, dann müssen Sie den Zustand wiederherstellen, wie Sie diese rekursive Funktion erneut aufrufen. Es gibt keine allgemeine Möglichkeit, einen solchen Zustand zu speichern, jedoch kann wahrscheinlich eine Vorlage erstellt werden. Etwas wie folgt aus:

class Crawler<T> { 
    LinkedList<T> innerState; 
    Callback<T> callback; 
    constructor Crawler(T base,Callback<T> callback) { 
     innerState=new LinkedList<T>(); 
     innerState.push(base); 
     this.callback=callback; // I want functions passed here 
    } 
    T recursiveFunction() { 
     T base=innerState.pop(); 
     T result=return recursiveInner(base); 
     if (!result) innerState.push(base); // full recursion complete 
     return result; 
    } 
    private T recursiveInner(T element) { 
     ArrayList<T> c=callback.getAllSubElements(element); 
      T d; 
      for each (T el in c) { 
       if (innerState.length()>0) { 
        d=innerState.pop(); 
        c.skipTo(d); 
        el=d; 
        if (innerState.length()==0) el=c.getNext(); 
        // we have already processed "d", if full inner state is restored 
       } 
       T result=null; 
       if (callback.testFunction(el)) result=el; 
       if ((!result) && (callback.recursiveFunction(el))) result=recursiveInner(el); // if we can recurse on this element, go for it 
       if (result) { 
        // returning true, go save state 
        innerState.push(el); // push current local state to "stack" 
        return result; 
       } 
      } // end foreach 
      return null; 
     } 
} 
interface Callback<T> { 
    bool testFunction(T element); 
    bool recursiveFunction(T element); 
    ArrayList<t> getAllSubElements(T element); 
} 

Hier skipTo() ist eine Methode, die den Iterator auf c modifiziert zu versehen Element zu zeigen. Callback<T> ist ein Mittel zum Übergeben von Funktionen an eine Klasse, die als Bedingungsprüfung verwendet werden soll. Sagen Sie "Ist T ein Ordner" für die rekursive Prüfung, "Ist T a *. Txt" für die Rückfrage, und "getAllSubclassElements" sollte auch hier gehören. Die for each-Schleife ist mangels Wissen darüber, wie man mit modifizierbaren Iteratoren in Java arbeitet, bitte an den tatsächlichen Code anzupassen.

Answer 3

Die einzige Möglichkeit, die ich mir vorstellen könnte, wäre, den rekursiven Tree-Walk in einem separaten Thread auszuführen und diesen Thread nacheinander dem Hauptthread zuzuführen. (Der Einfachheit halber könnte man eine beschränkte Warteschlange für die Zustellung verwenden, aber es ist auch möglich, wait/notify, ein Sperrobjekt und eine einzige gemeinsam genutzte Referenzvariable zu implementieren.)

In Python wäre dies beispielsweise der Fall eine gute Passform für coroutines. Leider hat Java kein direktes Äquivalent.

Ich sollte hinzufügen, dass die Verwendung von Threads wahrscheinlich erhebliche Overhead in der Synchronisierung und Thread-Kontextwechsel. Durch die Verwendung einer Warteschlange werden diese um einen gewissen Grad reduziert, vorausgesetzt, dass die Rate des "Produzierens" und "Konsums" gut übereinstimmt.