[R] speeding up a recursive function

[Prof Brian Ripley]

On Sun, 2 Apr 2006, Federico Calboli wrote:

> is there any general advice about speeding up recursive functions
> (not mentioning 'don't use them')?

Well, that's very general (did you mean recursive functions in R or C or
what?).  Recursion is not particularly slow in R, and you are limited to a 
depth of a most a few thousand.  E.g.:

> f <- function(x) if(x > 0) f(x-1)
> system.time(for(i in 1:100) f(2000))
[1] 0.59 0.00 0.60   NA   NA

which is 3 usec per call.

One piece of advice is to keep memory usage down, as in many of the
examples I have looked at the speed issue was actually a memory issue,
with datasets being copied at each level.

-- 
Brian D. Ripley,                  ripley at stats.ox.ac.uk
Professor of Applied Statistics,  http://www.stats.ox.ac.uk/~ripley/
University of Oxford,             Tel:  +44 1865 272861 (self)
1 South Parks Road,                     +44 1865 272866 (PA)
Oxford OX1 3TG, UK                Fax:  +44 1865 272595