|Don't ask to ask, just ask|
Re: Re: problem prototyping a self-recursing functionby thraxil (Prior)
|on Dec 08, 2001 at 00:15 UTC||Need Help??|
here's a benchmark of the two:
the results on my system (1GHz P4 w/ 512MB) for $trials = 50000:
loop: 3 wallclock secs ( 2.09 usr + 0.01 sys = 2.10 CPU) @ 23809.52/s (n=50000) recursive: 2 wallclock secs ( 2.19 usr + 0.01 sys = 2.20 CPU) @ 22727.27/s (n=50000)
for $trials = 500000:
loop: 21 wallclock secs (20.91 usr + 0.06 sys = 20.97 CPU) @ 23843.59/s (n=500000) recursive: 23 wallclock secs (21.89 usr + 0.09 sys = 21.98 CPU) @ 22747.95/s (n=500000)
so i'd be inclined to say that there isn't really a very significant difference between the looped and recursive versions in this case (not surprising since the subroutine doesn't return anything and thus the perl interpreter ought to be able to optimize things fairly well).
of course, things change a little if you increase the level of recursion. eg, changing it to $count < 40 in the recursive one and to $count..39 in the loop version (and $trials = 50000):
loop: 17 wallclock secs (16.46 usr + 0.09 sys = 16.55 CPU) @ 3021.15/s (n=50000) recursive: 24 wallclock secs (23.48 usr + 0.12 sys = 23.60 CPU) @ 2118.64/s (n=50000)
increase the level of recursion much more and you run into the real problem of doing recursion in perl. it limits the level of recursion so you start getting runtime errors if you go over something like 50 deep (i'm not sure exactly what the level is). IMO, this, not the efficiency reason, is why you may want to avoid heavy use of recursion in perl.
the issue of loop vs recursion efficiency is highly dependent on the language used. it's been my experience with functional languages like ML that recursion is significantly more efficient than looping because the language is designed for it and the compiler/interpreter is optimized for recursion. i haven't done much LISP programming but i'm surprised that you had efficiency problems with recursion; i thought it was one of those recursion optimized languages.