loop/recur is explicit tail recursion, and therefore will only work if the
"recur" is in the tail position, i.e. the last form evaluated.
For example, this function is tail recursive:
(defn sum [coll result]
(if (seq coll)
(sum (rest coll) (+ result (first coll)))
0))
While this function is not:
(defn sum [coll]
(if (seq coll)
(+ (first coll) (sum (rest coll)))
0))
In the latter case, the last function called is "+", not "sum".
The reason this is important is that tail-recursive functions can be
optimised. Normally recursive functions build up stack frames for each
iteration. That's why recursive functions are vulnerable to stack overflow
errors. But if the recursion is the last form in the function, there's no
need to retain the stack frame, because the function is going to end
immediately afterward.
Most functional languages have this tail-call-optimisation, or TCO, that
allows them to use recursion without blowing the stack. Clojure doesn't
have automatic TCO, because it's limited by the JVM, so instead it has
explicit TCO in the form of "recur".
You can actually use "recur" without the outer "loop":
(defn sum [coll result]
(if (seq coll)
(recur (rest coll) (+ result (first coll)))
0))
This will work the same as the first example, but has the advantage of not
using up the stack.
As you correctly assert, loop/recur is equivalent to a function:
(defn sum [coll]
(fn [acc]
(if (seq coll)
(sum (rest coll) (+ result (first coll)))
0))
0))
Which is equivalent to:
(defn sum [coll]
(fn [acc]
(if (seq coll)
(recur (rest coll) (+ result (first coll)))
0))
0))
Which is equivalent to:
(defn sum [coll]
(loop [acc 0]
(if (seq coll)
(recur (rest coll) (+ result (first coll)))
0))))
- James
On 3 June 2014 22:00, Mike Fikes <mikefi...@me.com> wrote:
> I'm trying to “internalize” loop/recur as being a functional construct.
>
> I'm sure I'm not alone in this: I initially struggled with it, with my
> view unduely influenced by its implementation, especially when multiple
> loop heads are present. (It could be viewed as vulgar but necessary
> imperative optimization, playing tricks with the instruction pointer).
>
> Here is a line of reasoning that I'm interested in comments on:
>
> Take this example:
>
> (defn vrange [n]
> (loop [i 0 v []]
> (if (< i n)
> (recur (inc i) (conj v i))
> v)))
>
>
> This can be rewritten applying a named inline function that closes over n:
>
> (defn vrange2 [n]
> ((fn loop-recur [i v]
> (if (< i n)
> (loop-recur (inc i) (conj v i))
> v)) 0 []))
>
>
> Then, this could be further transformed:
>
> (defn loop-recur [i v n]
> (if (< i n)
> (loop-recur (inc i) (conj v i))
> v))
>
> (defn vrange3 [n]
> loop-recur 0 [] n)
>
>
> which is clearly functional.
>
> I'm cool with this view. It with it, you see recur not so much as as not
> “jumping” to the nearest loop head, but instead as returning a value that
> results from ”calling” a function, where that function is kind-of defined
> by the loop head.
>
> I was wondering? Is the above transformation always possible, even given
> multiple loop heads? Is it always this simple, or are there corner cases
> that this naïve view misses?
>
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clojure@googlegroups.com
> Note that posts from new members are moderated - please be patient with
> your first post.
> To unsubscribe from this group, send email to
> clojure+unsubscr...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to the Google Groups
> "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to clojure+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
