NewLisp not Tail Recursive?

[AlexPeake]

I Try:



(define (fact x ans)

  (if (< x 1)

   ans

   (fact (- x 1) (* x ans))))



Which is Tail Recursive and yet I still get stack overflow??

[HPW]

Alex,



welcome on the forum.



Lutz did a comment here:



http://www.alh.net/newlisp/phpbb/viewtopic.php?t=128">http://www.alh.net/newlisp/phpbb/viewtopic.php?t=128





Lutz comment:

newLISP does no tail-recursion optimization. Fortunately those tail-recursive routines are also the easiest to re-write them to an iterative pattern.

[AlexPeake]

Thanks for the "work-around".



Kind of misses the point of using Lisp/Scheme?

[Lutz]

Here is a non-recursive version of factorial:



(define (fact n)  (apply mul (sequence 1 n)))



Its is also much faster then the recursive version. You also could use * instaead of mul, but it would flow over to a max int of 2147463647 very fast. the 'mul' does foating point calculation.



I think that introductory books on LISP stress recursion too much, many of the examples typically published in that context are much better solved with an iteration.



I know that the topic recursion versus iteration is a very 'religous' one in the LISP community. newLISP's focus is more on solving 'real world' problems with LISP.



BTW,  welcome to our discussion group Alex!



Lutz

[Sammo]

(define (fact n) (apply mul (sequence 1 n)))



(fact 100) --> 9.332621544e+157

(fact 150) --> 5.713383956e+262

(fact 500) --> crash!

[Lutz]

This is due to incorrect handling of INF in the Win32 version and is fixed in the version 7.4.0rc1 posted this morning in:



http://newlisp.org/download/development/">http://newlisp.org/download/development/



(fact 500) => +INF





Lutz

[Sammo]

Outstanding!

[Lutz]

Thanks Sam, I always joke: "math is the most difficult thing for a computer to do"



Getting all the NaN and over/underflow right on the Win32 version has taken some time. On Linux/BSD and friends it's all handled pretty much automatically by the GCC compiler and you don't have to do much. On Borland C-Builder (which is an excellent compiler in my opinion) it took some time to make it work exactly like on the other platforms.



Lutz