loop recur vs recursion

[bOR_]

Hi all,

I wondered if there is a difference between using loop-recur or merely
writing a recursive function. The main difference I found thus far was
that the loop-recur can suffice with less arguments, but the recursive
functions seem to be shorter, and perhaps more elegant?

(defn construct-atom
"translates a number n into an set of letters of size n"
[construct length]
(if (< (count construct) length)
(construct-atom (conj construct (char (+ (rand-int amino_acids)
65))) length)
construct))

(defn construct-atom-loop
"translates a number n into an set of letters of size n"
[n]
(let [base_construct #{}]
(loop [construct base_construct]
(if (< (count construct) n)
(recur (conj construct (char (+ (rand-int amino_acids) 65))))
construct))))

[Kevin Downey]

the jvm does not do TCO, loop/recur allows for functional looking
recursion on the jvm with constant stack size.

--
And what is good, Phaedrus,
And what is not good—
Need we ask anyone to tell us these things?

[bOR_]

In this case, the depth of the recursion would be at maximum 21
(number of different types of amino acids), and the function itself
not often called. Is stack size something to worry about at those
depths?

[Daniel Renfer]

Even if you don't think you'll run into the possibility of blowing
your stack, it's still a good idea to use recur when doing tail call
recursion. The compiler will help you out by making sure it really is
a tail call.

Remember, recur isn't just for loop. It works with functions too.

[Rich Hickey]

On Nov 29, 2008, at 6:49 AM, Daniel Renfer wrote:

> Even if you don't think you'll run into the possibility of blowing
> your stack, it's still a good idea to use recur when doing tail call
> recursion. The compiler will help you out by making sure it really is
> a tail call.
>
> Remember, recur isn't just for loop. It works with functions too.

In case that isn't clear, it means that anywhere you would do a self
call in a tail position you can replace it with recur to ensure no
stack growth, e.g. the first example could have been written:

(defn construct-atom
"translates a number n into an set of letters of size n"
[construct length]
(if (< (count construct) length)

(recur (conj construct (char (+ (rand-int amino_acids) 65))) length)
construct))

recur will goto the nearest enclosing loop or fn.

Rich

[.Bill Smith]

As often as this comes up, I wonder if TCO and loop/recur deserve
their own section in the reference section.

Bill

[bOR_]

>
> (defn construct-atom
>   "translates a number n into an set of letters of size n"
>   [construct length]
>   (if (< (count construct) length)
>     (recur (conj construct (char (+ (rand-int amino_acids) 65))) length)
>     construct))
>
> recur will goto the nearest enclosing loop or fn.
>
> Rich
>

Ah. I was looking for something like that. The Fibonacci example on
the 'special forms' website does use both a fn and a loop, which was
somewhat confusing. Perhaps an example without loop would indeed help.
Thanks!

[RZez...@gmail.com]

On Nov 29, 7:52 am, Rich Hickey <richhic...@gmail.com> wrote:
> On Nov 29, 2008, at 6:49 AM, Daniel Renfer wrote:
>
> > Even if you don't think you'll run into the possibility of blowing
> > your stack, it's still a good idea to use recur when doing tail call
> > recursion. The compiler will help you out by making sure it really is
> > a tail call.
>
> > Remember, recur isn't just for loop. It works with functions too.
>
> In case that isn't clear, it means that anywhere you would do a self  
> call in a tail position you can replace it with recur to ensure no  
> stack growth, e.g. the first example could have been written:
>
> (defn construct-atom
>   "translates a number n into an set of letters of size n"
>   [construct length]
>   (if (< (count construct) length)
>     (recur (conj construct (char (+ (rand-int amino_acids) 65))) length)
>     construct))
>
> recur will goto the nearest enclosing loop or fn.
>
> Rich
>
>

What about the case where recursing from a catch clause?

e.g.

(defn prompt-for-int [prompt junk-allowed default]
(let [input (prompt-read prompt)]
(try (Integer/valueOf input)
(catch NumberFormatException _
(if junk-allowed
default
(prompt-for-int prompt junk-allowed default))))))


If I use recur I get the following exception:

java.lang.UnsupportedOperationException: Cannot recur from catch/
finally

I'm sure there is a more idiomatic way to write this. Maybe that's
the question I really need to ask? How can I rewrite the above?

[Michael Wood]

I don't know the technical reason for disallowing recur from within a
catch/finally. A more restricted case came up recently in this
thread:

http://groups.google.com/group/clojure/browse_thread/thread/2c9f018886e71ee3/05920a3ffd7250d2?lnk=gst#05920a3ffd7250d2

But that won't help with your case.

I suppose you could use a helper function that returns nil if there
was junk and then recur if you get nil back from the helper?

--
Michael Wood <esio...@gmail.com>

[RZez...@gmail.com]

On Nov 30, 3:51 pm, "Michael Wood" <esiot...@gmail.com> wrote:

> http://groups.google.com/group/clojure/browse_thread/thread/2c9f01888...

>
> But that won't help with your case.
>
> I suppose you could use a helper function that returns nil if there
> was junk and then recur if you get nil back from the helper?
>
> --

> Michael Wood <esiot...@gmail.com>

I've read that thread. Rich ends it by stating "it's an arbitrary
restriction because of complexity."

The helper function would work just fine, and if this was code for
some important project then I probably would go that route. I guess I
still feel my initial solution should be appropriate, but I would like
to be able to do it with recur as to avoid overflow. Any other
solutions that would avoid a helper function? Not just for my
particular case, but anytime that one is calling recur from a catch
clause?

[Chouser]

On Sun, Nov 30, 2008 at 5:52 PM, rzez...@gmail.com <RZez...@gmail.com> wrote:
>
> Any other solutions that would avoid a helper function? Not just
> for my particular case, but anytime that one is calling recur from a
> catch clause?

Generally, collect the information you need from the catch clause and
return it to a context where recur can be called if needed.

(defn prompt-for-int [prompt junk-allowed default]
(let [input (prompt-read prompt)

num (try (Integer/valueOf input)
(catch Exception _ :fail))]
(if (= num :fail)
(if junk-allowed
default
(recur prompt junk-allowed default))
num)))

Note that the above ugliness is caused at least in part by a mismatch
between the Java API and Clojure idioms. If 'Integer/valueOf' were a
Clojure function, I would expect nil to signal an error and any
Integer returned to be valid:

(defn parse-int [string]
(try (Integer. string) (catch Exception _)))

This would allow for a much cleaner definition of prompt-for-int:

(defn prompt-for-int [prompt junk-allowed default]

(or (parse-int (prompt-read prompt))

(if junk-allowed
default
(prompt-for-int prompt junk-allowed default))))

Or, since a default only makes sense if it might be returned:

(defn prompt-for-int
([prompt] (or (prompt-for-int prompt nil) (recur prompt)))
([prompt default] (or (parse-int (prompt-read prompt)) default)))

--Chouser

[RZez...@gmail.com]

On Nov 30, 7:47 pm, Chouser <chou...@gmail.com> wrote:

That all makes sense and your solutions are succinct. I agree with
your observation that the ugliness comes from a Java/Clojure
mismatch. I also need to re-wire my brain to think in a more
functional and LISPy style.

Thanks, Chouser.