# recursive tree walk -> iterative #barcap

Suppose there’s a deep directory tree (no hard/soft links) with millions of files and directories. Write a tree walker to list files excluding directories. For memory efficiency, turn the recursive algorithm into iterative.

I feel recursive thinking is far more powerful than iterative, because it solves problems otherwise unsolvable. Most classic algo problems fall into this category. I always try to train myself to think recursively. In this regard, It’s good to study and compare iterative algorithms. What kind of recursive algo can be converted to iterative? I feel only simple ones.

Inspired by the article in the link, here are my rules for converting recursion to iteration

Rule: one push (on the stack) per call of the recursive func.

Rule: a stack to hold the arg of the recursive calls, in the correct order. Assuming m(1) -> m(2) -> m(3), then we should push 1,2,3 on the stack. Ideally, the order in our stack should match the recursive call stack.

Rule: since it’s a stack, you remove from the top and add to the top too.

Rule: first step when you reenter the while(not_empty) loop, you simulate a new recursive call by _popping_ the stack. The popped item is no longer a “pending” todo item.

Next Question: how to parallelize? You don’t know how deep each sub-tree is.

`public class LowLatencyTreeWalker { static java.util.LinkedList envelopesToOpen = new java.util.LinkedList(); static void factorial() { // a simple iterative solution to compute  // factorials  envelopesToOpen.add(6);  long ret = 1;  while (!envelopesToOpen.isEmpty()) {   int currNum = envelopesToOpen.removeLast();   System.out.println(ret = ret * currNum);   if (currNum > 1)    envelopesToOpen.add(currNum - 1);  } } static void walkTree(String args[]) { // a harder iterative algorithm for  // tree-walk  envelopesToOpen.add(new File("C:/"));  while (!envelopesToOpen.isEmpty()) {   // once we open an envelope, we remove from the todo stack   File f = envelopesToOpen.removeLast();   System.out.println(f.getAbsolutePath());   if (f.listFiles() != null)    envelopesToOpen.addAll(Arrays.asList(f.listFiles()));  } }}`