Roger Hui wrote: >> (a) Avoid recursion, unless you are memoizing the results. > > I wonder about this one. A recursion whose results > are atoms (or involve small amounts of data) could > be inefficient without memoization. Otherwise there > is nothing much wrong with recursion in J. e.g. >
Roger: I take your points. In particular 1. I was thinking about small result size for memoization. (By the way, is this still going to be in J6.02?) 2. I have nothing against tail recursion. 3. I was partly put off a while ago when the recursion depth was too small: now it is OK. The types of problems where I have had problems concern naturally recursive problems where each step is quite small and conditionals are involved. In my experience, J then suffers in comparison to C-like languages, although the problem can often be reformulated to give excellent performance in a way it could not be in C. For example, suppose p(i,j,n) is a boolean function returning 1 only if there is a path in a graph of length n from vertex i to vertex j. This can be formulated recursively as if n=0, p(i,j,n)=1 iff i=j if n>0, p(i,j,n)=1 only if there exists a vertex k with P(i,k,1)=1 and P(k,j,n-1)=1. Of course, in this case, we can solve the problem for all i,j by taking the nth power of the adjacency matrix. In general it may be hard to go from the recursive formulation to the more direct approach, and requires replacing the depth-first search often implied by recursion by breadth-first. Best wishes, John ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
