[metapost] recursion in MP/ MF [was: all intersections between two paths]

[Boguslaw Jackowski]

Hi,

LaurenceF> I _always_ try to eliminate recursion in my programs
LaurenceF> wherever possible, and it often is.  I haven't read your
LaurenceF> code, so I don't know whether it is in this case.  However,
LaurenceF> I think it would be worthwhile to consider whether you
LaurenceF> couldn't just put the subpaths onto an array and loop over
LaurenceF> the array until some condition is met.

I like recursion, because it helps to express the ideas (usually) in
a concise way. Laurence apparently belongs to the people avoiding 
recursion. Which approach is better? We, in Poland, call questions of this 
kind ``the discussion on the superiority of Christmas over Easter''. ;-)

HansH> there's nothing wrong with recursion; in tex/mp, try to use tail
HansH> recursion and then there are no limits

Tail recursion can be nearly automatically converted to a loop (without
employing a stack), so tail recursion is not a problem.

The ``true'' recursion, however, is still discriminated in MP/MF -- the
parameter stack is to small to use recursive techniques in practice.
In 1994, during the (mentioned in one of my previous letters) conference
in Sobieszewo, Poland, Marek Ry\'cko and I complained about it; then, a few
years later, I resumed the problem on the <metafont at ens.fr> list, giving the
following example:

% --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
vardef quicksort@#(expr i,j) =
% sorts numeric array |@#[i..j]| using Tony Hoare's ``quick sort'' method;
 if i<j:
  save k,l,sort_cell;
  sort_cell:=@#[i];
  l:=i;
  for k:=i+1 upto j:
   if @#[k]<sort_cell:
     @#[l]:=@#[k]; @#[k]:=@#[l+1];
    l:=l+1;
   fi
  endfor
  @#[l]:=sort_cell;
  quicksort@#(i,l-1); quicksort@#(l+1,j);
 fi
enddef;

% n:=28; % SUCCESS
n:=29;   % FAILURE

for i:=1 upto n: A[i]:=n-i; endfor

quicksort A(1,n); showvariable A;

end.
% --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

Now is much better: the program breaks for much larger n, i.e., n=31...

Cheers -- Jacko

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
 Bogus\l{}aw Jackowski: B_Jackowski at GUST.ORG.PL
----------------------------------------------------------------
 Hofstadter's Law: It always takes longer than you expect, even
                   when you take into account Hofstadter's Law.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-