calling recur from catch or finally

Clojure doesn’t have tail recursion, but does support the recur form. Let’s take a quick look at how it’s used. Consider a function that sums up a list of numbers to an accumulator:

(defn add-numbers [acc numbers]
  (if (empty? numbers)
    acc
    (add-numbers (+ acc (first numbers)) (rest numbers))))

Lets ignore all the ways this can be done without the silly implementation above. Here it is in action:

user> (add-numbers 10 (range 10))
55

And here’s the problem with it:

user> (add-numbers 10 (range 10000))
; Evaluation aborted.
No message.
  [Thrown class java.lang.StackOverflowError]

The reason, of course, is that being a self-recursive function that calls itself explicitly, it blows the stack. Clojure has a way to get around this, via the recur form:

(defn add-numbers [acc numbers]
  (if (empty? numbers)
    acc
    (recur (+ acc (first numbers)) (rest numbers))))

And here is proof that it works:

user> (add-numbers 10 (range 10000))
49995010

Now, let’s look at a case where one might want to recurse from inside a catch or finally block. A use-case is a function like connect-to-service, that must retry the connection if the service is unavailable. An easy way to implement it is to catch the exception thrown when the attempt at connecting fails, then wait a few seconds, and try again by recursing. Here’s a contrived example of a function that recurs from catch:

(defn catch-recurse [n i]
  (try
    (if (> n i)
      (/ i 0)
      n)
    (catch Exception e
      (recur n (inc i)))))

The problem, of course, is that Clojure complains:

Cannot recur from catch/finally
  [Thrown class java.lang.UnsupportedOperationException]

So what to do? One way is to make the call explicitly, and hope that it won’t blow the stack:

(defn catch-recurse [n i]
  (try
    (if (> n i)
      (/ i 0)
      n)
    (catch Exception e
      (catch-recurse n (inc i)))))

It could blow the stack, though, depending:

user> (catch-recurse 100 1)
100
user> (catch-recurse 10000 1)
; Evaluation aborted.
No message.
  [Thrown class java.lang.StackOverflowError]

As pointed out, this may blow the stack, but it may not, depending on your situation. If you know it won’t, then this may be OK. Here’s a way to avoid this situation completely, using trampoline. First, a minor change to catch-recurse:

(defn catch-recurse [n i]
  (try
    (if (> n i)
      (/ i 0)
      n)
    (catch Exception e
      #(catch-recurse n (inc i)))))

Notice that in the case of an exception, we return a thunk. Now, to use our new function:

user> (trampoline catch-recurse 100 1)
100
user> (trampoline catch-recurse 10000 1)
10000

And there you have it. The common use-case of trampoline is to handle mutually recursive functions where recur isn’t useful. It checks to see if the return value of the function it’s passed in is another function. If so, it calls it. It repeats the process until a non-function value is returned, which it then itself returns. Very useful!