Retaining the stack position of a recursive function between calls

Question

This question is general, but I feel it is best explained with a specific example. Let's say I have a directory with many nested sub directories and in some of those sub directories there are text files ending with ".txt". A sample structure could be:

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

I'd be interested if there were a way in Java to build a method that could be called to return the successive text files:

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

Here is the challenge: No internal list of all the text files can be saved in the crawler object. That is trivial. In that case you'd simply build into the initialization a method that recursively builds the list of files.

Is there a general way of pausing a recursive method so that when it is called again it returns to the specific point in the stack where it left? Or will we have to write something that is specific to each situation and solutions necessarily have to vary for file crawlers, org chart searches, recursive prime finders, etc.?

Answer 1

If you want a solution that works on any recursive function, you can accept a Consumer object. It may look something like this:

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

For a bunch of files, it might look like this:

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

You can then call it with:

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

Adapt as necessary.

Answer 2

I think the state should be saved while you return from your recursive function, then you need to restore the state as you call that recursive function again. There is no generic way to save such a state, however a template can probably be created. Something like this:

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);
}

Here, skipTo() is a method that modifies the iterator on c to point to provided element. Callback<T> is a means to pass functions to class to be used as condition checkers. Say "Is T a folder" for recursive check, "Is T a *.txt" for return check, and "getAllSubclassElements" should also belong here. The for each loop is fron lack of knowledge on how to work with modifiable iterators in Java, please adapt to actual code.

Answer 3

The only way I can think of that would meet your exact requirement would be to perform the recursive tree walk in a separate thread, and have that thread deliver results back to the main thread one at a time. (For simplicity you could use a bounded queue for the delivery, but it is also possible to implement is using wait / notify, a lock object and a single shared reference variable.)

In Python, for example, this would be a good fit for coroutines. Unfortunately, Java doesn't have a direct equivalent.

I should add that using threads is likely to incur significant overhead in synchronization and thread context switching. Using a queue will reduce them to a degree provided that rate of "producing" and "consuming" is well matched.