Tree recursion

Remember: Recursion is loops for trees

The magic of recursion is that every recursive call keeps track of where it is in its own computation.

public int fib(int n) {
  return n < 2 ? n : fib(n - 2) + fib(n - 1);
}

At any given call to fib the chain of calls that led to it are all keeping track of where they are in their own computation; did they just make their call to fib(n - 2) or the one to fib(n - 1)?

The calls fib(5) makes

Three kinds of recursion

• Linear recursion. Kind of silly. Just use a loop.
• Tree recursion with redundancy in the tree
• Tree recursion with no real redundancy in the tree

Finding the length of a linked list using recursion is linear recursion.

It is a bit silly in languages like Java that aren’t built around recursion because method calls use resources that loops don’t.

Some problems, such as computing the nth Fibonacci number, are naturally defined recursively but expand out into a tree with lots of duplication.

Such problems can often by implemented much more efficiently using techniques such as memoization and dynamic programming that transform the natural recursive computation into one that doesn’t do a lot of redundant work.

Problems that are tree-shaped with little to no redundancy in the tree are best solved recursively. Usually the depth of such trees is not too bad as long as you’re not using Python.

It is possible to turn any recursive solution into an iterative one if you introduce your own explicit stack.

Computing disk usage

public long diskUsage(File file) {
  if (!file.isDirectory()) {
    return file.size();
  } else {
    int size = 0;
    for (File child : f.children()) {
      size += diskUsage(child);
    }
    return size;
  }
}

public long diskUsage(File file) {
  int total = 0;
  List<File> stack = new ArrayList<>();
  stack.add(file);
  while (!stack.isEmpty()) {
    File f = stack.removeLast();
    if (!f.isDirectory()) {
      total += f.size();
    } else {
      stack.addAll(f.children());
    }
  }
  return total;
}

In this case the iterative one is not too bad.

But it’s also unlikely that you have such deeply nested folders on your computer that the recursive one is going to be a problem.