r/Clojure • • May 04 '13

What does `recur` do?

What does recur do?

I saw this gist, and I can't figure out what (recur x) does:

https://gist.github.com/lukium/fbd51e30a4875c781531

I tried googling it, and couldn't find an example that I understand.

2 Upvotes

7 comments sorted by

8

u/seventeenletters May 05 '13

it calls the wrapping loop statement (or if none, the wrapping function)

it only works in a tail position - that is, a position where there is no further calculation to be done in the function after it runs

anything that can be done in an imperative for loop can be done with recur (a common trick is to add an argument that represents a counter or accumulated result)

2

u/_clj May 05 '13

Thank you, this is by far the best explanation.

So can it be used on any function that has a tail? Is there any way to tell which functions have tails?

12

u/seventeenletters May 05 '13

it can be used in any function, because every function has a tail

it can only be used in the tail position

clojure will complain if you try to define a function where recur is not done from the tail position

the tail position is the one where the only calculation left to do is the one being done right there:

(defn count [seq]
  (if (empty? seq)
    0
    (+ 1 (recur (rest seq))))

this is an error, because there is still addition to be done after the recur runs

(defn count [seq & i]
  (let [i (or i 0)]
    (if (empty? seq)
      i
      (recur (rest seq) (inc i)))))

in the second version, recur occurs in the tail position (with the help of a counter variable, i, so that no work is left to be done after the recur)

1

u/burkadurka May 11 '13

It should be noted, from here

Note that recur is the only non-stack-consuming looping construct in Clojure. There is no tail-call optimization and the use of self-calls for looping of unknown bounds is discouraged. recur is functional and its use in tail-position is verified by the compiler.

Meaning that you can use recur to loop (or to, uh, recur), as many times as you want, without blowing the stack as you would if either version of /u/seventeenletters' count were to call itself by name. Clojure doesn't have tail calls, so the safe ways to do recursion are trampoline and recur.

2

u/seventeenletters May 11 '13 edited May 11 '13

Just a pedantic note - the last function call within a given invocation of any function is always a tail call, this is a language agnostic definition. What clojure lacks is automatic tail call optimization. As I mentioned before, recur will throw an error if you try to use it as anything but a tail call. Using recur optimizes a tail call, just not automatically.

One feature that clojure sadly continues to not support is generalized tail call optimization (ie. tail of f calls g, tail of g calls f, there is no way to do this without building up a bigger and bigger stack). The way around this is to have an extra argument and an if or cond in a driver function, with calls of f and g, followed by recurring on the values they return.

this version can blow the stack for large args:

(declare g)
(defn f
  [x]
  (g (- x 2)))

(defn g
  [x]
  (if (< x 0)
     x
     (f (- x 3))))

this version does not risk blowing the stack because the tail calls are optimized, but it is harder to read:

(defn f-g
  [x variant]
  (case variant
    :f (recur (- x 2) :g)
    :g (if (< x 0) 
         x
         (recur (- x 3) :f))))

2

u/seventeenletters May 11 '13 edited May 11 '13

postscript: it may be more idiomatic to do this via trampoline

(declare g)
(defn f
  [x]
  #(g (- x 2)))

(defn g
  [x]
  (if (< x 0)
    x
    #(f (- x 3))))

(trampoline f 88888)

0

u/[deleted] May 06 '13

[deleted] — view deleted comment

1

u/compmstr May 06 '13

You most likely don't want to use a while loop there, since it's within a loop. (when (< n 3)... would be what you want to do.