newlispfanclub.alh.net

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??

Alex,

welcome on the forum.

Lutz did a comment here:

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.

Thanks for the "work-around".

Kind of misses the point of using Lisp/Scheme?

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

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

(fact 100) --> 9.332621544e+157
(fact 150) --> 5.713383956e+262
(fact 500) --> crash!

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/

(fact 500) => +INF


Lutz

Outstanding!

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