Programming Puzzles

If you are used to Lisp-like constructs, tail recursion can give solutions that are both idiomatic and efficient.

[0] https://en.wikipedia.org/wiki/Tail_call

Lots of problems have vastly simpler recursive solutions. Try putting a recursive descent parser into a loop. Plenty of tree walking/formatting/analyzing algorithms are much cleaner using recursion. Recursively walking directory structures is cleaner using recursion. Many puzzles, such as Tower of Hanoi, are cleaner with recursion. Many sort algorithms, like merge sort, quicksort, etc., are cleaner with recursion. I could find plenty more algorithms where recursion makes the solution cleaner, simpler (hence less error prone), and sometimes even faster to execute.

And some algorithms use mutual recursion to solve problems - often putting those into a non-recursive formulation results in incredibly messy code. Mutual recursion is powerful enough that F# (among others) added an entire keyword to the language simply to support it.

And since many languages do proper tail recursion, there is no penalty for using it properly.

Which would you prefer?

  def msort(xs, lo=None, hi=None):
    if lo is None:
      lo = 0
      hi = len(xs)
    if hi-lo < 2:
      return
    mid = lo + (hi-lo) // 2
    msort(xs, lo, mid)
    msort(xs, mid, hi)
    merge(xs, lo, mid, hi)

  def msort(xs):
    s = [[0, len(xs) // 2, len(xs), "step 1"]]
    while s:
      lo, mid, hi, step = xs[-1]
      if step == "step 1":
        if hi-lo < 2:
          s.pop()
        else:
          s[-1][3] = "step 2"
          s.append([lo, lo + (mid-lo) // 2, mid, "step 1"])
      elif step == "step 2":
        s[-1][3] = "step 3"
        s.append([mid, mid + (hi-mid) // 2, hi, "step 1"])
      else:
        s.pop()
        merge(xs, lo, mid, hi)

Okay, here's the very recent problem I had to solve. There is a huge dump of a VM heap, represented as a key-value map: the values are either simple atomic values or compound structures that have addresses (keys into this map) as their parts. There is a list of "entry points" into the heap: addresses of the GC roots in the heap. The problem is to reconstruct the values stored in the heap. E.g., reconstructing starting from "heap(10)" in this heap:

    heap(10): cons(int(1),heap(18))
    heap(18): cons(int(2),heap(20))
    heap(20): cons(int(3),nil)

should result in

   [1, 2, 3]

Here's the thing: recursive walk is totally straightforward:

    def restore(v):
        if v.kind...
        elif v.kind == 'tuple':
            return Tuple([restore(v[i]) for i in range(v.arity)])
        elif v.kind == 'cons':
            return List(restore(v[0]), restore(v[1]))
        elif v.kind...
        else:
            return UnknownValue()

But since Python has a limit of 1000 nested function calls, restoration of long lists fails with StackOverflow, and so I had to rewrite it using manual stack. The result is sort of ugly, in fact, I had to use two stacks: one for temporary reconstructed pieces of data, one for "what to do next". Essentially it's implementing a variation of the shunting yard algorithm and while the resulting code is kinda clear in intent, it's still three times as long as the recursive version and is not obviously correct. In fact, I had to tweak it several times (including the introduction of the second stack) before I stopped seeing some (not all!) lists reconstructed in the reverse order.

Because you get a stack for free.

It's very natural for depth first search of a tree.

Manifestly, recursion is never strictly necessary, and is furthermore almost always slower, or anyway no faster, than you could do maintaining state "by hand".

But the recursive code can be much shorter, and easier to understand, because our languages have built-in apparatus to support it. They didn't always; original FORTRAN could not do recursion, and used no stack. The stack isn't free at runtime, but it's pretty cheap, and its fatal failure mode is rarely encountered nowadays.

In my work, I have always found the iterative version cleaner and faster, but that is an artifact of the kinds of problems I (and most people) solve. Having the iterative version enables more flexibility in details, because everything is explicit. E.g., escaping at the end can be much faster, and patching around errors actually possible.

Computer Science education loves to dwell on recursion far beyond its real-world usefulness, in part because CS professors carry a fondness for the Lisp of their youth, but also because arbitrarily complex problems that benefit from recursion are cheap to invent and easy to describe. In real life, recursion in any pure form rarely goes, usefully, more than three levels deep, but we like to make data structures that do.

At ITA, they did airline trip computations that would naturally recurse on the number of stops, but no one wants more stops, and time spent on possible trips with more than two is almost always wasted.

In a sense, recursion is like object-orientedness: an elegant pattern that fits many problems, but makes a poor basis for a world view or, exclusively, a language. Lisp and Smalltalk are not sidelined because of ignorance.

If you don't get that then I have bad news for you: it's a powerful technique that oftentimes makes code shorter, more elegant, and improves readability.

Like any other tool? If it's useful, use it, if it's not, don't. In many graph problems and parsing problems, it's useful, because it lets you express your solution more "naturally" with respect to the underlying domain. That's where I've used it seriously.