## NewLisp not Tail Recursive?

Q&A's, tips, howto's
AlexPeake
Posts: 2
Joined: Thu Dec 11, 2003 3:36 am

### NewLisp not Tail Recursive?

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
Posts: 1377
Joined: Thu Sep 26, 2002 9:15 am
Location: Germany
Contact:
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.
Hans-Peter

AlexPeake
Posts: 2
Joined: Thu Dec 11, 2003 3:36 am

### Tail Recursion

Thanks for the "work-around".

Kind of misses the point of using Lisp/Scheme?

Lutz
Posts: 5282
Joined: Thu Sep 26, 2002 4:45 pm
Contact:
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
Posts: 180
Joined: Sat Dec 06, 2003 6:11 pm
(define (fact n) (apply mul (sequence 1 n)))

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

Lutz
Posts: 5282
Joined: Thu Sep 26, 2002 4:45 pm
Contact:
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:

(fact 500) => +INF

Lutz

Sammo
Posts: 180
Joined: Sat Dec 06, 2003 6:11 pm