I already answered this question:
A recursion whose results are atoms
(or involve small amounts of data) could
be inefficient without memoization.
> The most common recursive pattern that
> memoization won't help with is the head,rest
> pattern that seems to form the basis of every
> list processing function in lisp, haskell and
> other functional languages:
J is not like the other functional languages.
----- Original Message -----
From: Pascal Jasmin <[EMAIL PROTECTED]>
Date: Tuesday, May 1, 2007 7:06 pm
Subject: Re: [Jprogramming] recursion -- was alchemy
>
> I find recursion performance in J to be poor.
>
> The most common recursive pattern that memoization won't help with
> is the head, rest pattern that seems to form the basis of every
> list processing function in lisp, haskell and other functional
> languages:
> f=: 3 :0
> if. 1>#y do. endofrecusionstep return. end.
> 'head rest'=. ({.;}.) y
> ( v1 head) v2 f rest NB. v1 and v2 are processing verbs
> )
>
> this type of process is slow and takes huge memory, and gives
> stack errors for lists that are of surprisingly modest length (10k
> or less)
>
> flisp =: 3 : 0
> if. 1=#y do. y return. end.
> 'head rest'=. ({.;}.) y
> head + flisp rest
> )
>
> ts '+/ i.4000'
> 3.26466279074e_5 17472
> ts 'flisp i.4000'
> 0.340178490394 48549056
>
> (,@:+/ -: flisp) i.20
> 1
>
> this version surprisingly takes even more memory:
>
> flisp2 =: 3 : 0
> if. 1=#y do. y return. end.
> ({. + flisp2@:}.) y
> )
>
> ts 'flisp2 i.4000'
> 0.243309521814 49654720
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
