[metapost] recursion in MP/ MF [was: all intersections between two
paths]
Boguslaw Jackowski
B_Jackowski at GUST.org.pl
Mon Jan 17 13:57:35 CET 2005
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.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
More information about the metapost
mailing list