[R] how to store recursive results

[Thomas Lumley]

On Fri, 22 Sep 2006, X.H Chen wrote:

> Hi Gabor,
>
> Thanks for pointing out this for me. However, what I try to get is how to 
> construct such form a function f that
>
> ret<-f(...),
>
> where ret contains the each recursive result from f, and meantime f consists 
> of no <<- operator. Do you have any idea how to implemet this. Thanks a lot 
> for your suggestions.
>

It depends on the situation. You can always pass the results back in a 
list or vector, eg

    cumfactorial<-function(n){
 	           if (n==0)
                       1
                    else c(1, n*cumfactorial(n-1))
    }


If you want to get the results out then you have to either accumulate and 
return them like this or use <<-, since return() and <<- are the only ways 
to get results out of a function.  As long as you don't use <<- to assign 
to variables outside the function it is a perfectly reasonable thing to do

If you were doing something like a Fibonacci sequence then assigning would 
be preferable

     fib<-function(n){
             memo<-new.env(hash=TRUE)
             fibrec<-function(m){
               if (m<=2) return(1)
               vm<-paste("v",m,sep="")
 	      if(exists(vm,envir=memo,inherits=FALSE))
                   return(get(vm,envir=memo,inherits=FALSE))
               rval<-fibrec(m-1)+fibrec(m-2)
 	      assign(vm,rval,envir=memo)
               rval
            }
           fibrec(n)
           sapply(ls(envir=memo),get, envir=memo)
          }

since the memoization converts the algorithm from exponential time to 
linear time.