Does Tail Recursion work properly ?

[Ragias]

I tried this code

reverse(ls) =>
  [] : []
  [x:xs] : reverse(xs) + [x]

print(reverse([1..1000]))

but it stack overflow

[Dave Newton]

You'd have to define a tail-recursive function in order to test tail recursion, I think.

[Ragias]

how can you define that ?
I mean clojure has recur
what loops does have ?

[Ragias]

However , I like the recur method
you do not have to write the name of the function twice
and when you see the word recur , you recognize that the function use tail recursion

[Steve]

Hi Ragias

 

It works when I try it.

Did you type it into the shell to execute immediately or execute it from a file?

I have found executing the file to be more reliable, also I define a main function rather than using the free-form style statements.

 

Steve.

[Ragias]

I did what you said

reverse(ls) =>
  [] : []
  [x:xs] : reverse(xs) + [x]

main ->
    print(reverse([1..1000]))

and It through an exception

Exception in thread "main" java.lang.ClassCastException: java.lang.StackOverflowError cannot be cast to java.lang.RuntimeException
    at loop.Executable.main(Executable.java:244)
    at loop.Loop.safeEval(Loop.java:60)
    at loop.Loop.run(Loop.java:30)
    at loop.Loop.main(Loop.java:23)

[Dave Newton]

You both may be running with different memory constraints. There are three issues: tail recursion, memory, and the cast.

The cast is likely a loop repl issue. You can increase your memory. The function isn't tail recursive from what I know of tail recursion, but it could be a loop-specific construct I'm not aware of (haven't played with it much).

Dave

(pardon brevity, typos, and top-quoting; on cell)

[Dhanji R. Prasanna]

The form of the "reverse" function you have showin is head-recursive, not tail-recursive. These are not concepts specific to Loop, but general functional concepts. The point is that the recursion occurs at the beginning of the function, so there is no way to perform TCO on it (there is theoretically head recursion elimination that's possible, but very few languages do anything like that).

The short answer is it is not possible to write reverse() tail-recursively. Even Haskell will stack overflow above a certain number of recursions.