Does R store the values of recursive functions that it has obtained?-CodePudding

I have used Mathematica for many years and have just started using R for programming. In both programs we can define recursive functions. In Mathematica there is a way to save values of functions. I am not sure if this is the default setting for R. Take the Fibonacci numbers for example. In Mathematica

fibonacci[0]=1;
fibonacci[1]=1;
fibonacci[n_]:=fibonacci[n-1] fibonacci[n-2];

Let's say to find fibonacci[10]. It needs to find all fibonacci[i] from i=2, ..., 9 first. After that, if we want to find fibonacci[11], then the program needs to go through the whole process to find all fibonacci[i] from i=2, ..., 10 again. It does not store the values it has obtained. A modification in Mathematica is

fibonacci[0]=1;
fibonacci[1]=1;
fibonacci[n_]:=fibonacci[n]=fibonacci[n-1] fibonacci[n-2];

In this way, once we have computed the value fibonacci[10], it is stored, and we do not need to compute it again to find fibonacci[11]. This can save a lot of time to find, say fibonacci[10^9].

The Fibonacci function in R can be defined similarly:

fibonacci = function(n) { 
    if (n==0 | n==1) { n } 
    else {fibonacci[n-1] fibonacci[n-2]}}

Does R store the value fibonacci[10] after we compute it? Does R compute fibonacci[10] again when we want to find fibonacci[11] next? Similar questions have been asked for other programmings.

Edit: as John has suggested, I have computed fibonacci[30] (which is 832040) and then fibonacci[31] (which is 1346269). It took longer to get fibonacci[31]. So it appears that the R function defined above does not store the values. How to change the program so that it can store the intermediate values of a recursive function?

CodePudding user response：

R does not do this by default, and similarly as you see Mathematica doesn't either. You can implement memoise yourself or use the memoise package.

fib <- function(i){
  if(i == 0 || i == 1)
    i
  else
    fib(i - 1)   fib(i - 2)
}
system.time(fib(30))
#   user  system elapsed 
#   0.92    0.00    1.84 
library(memoise)
fib <- memoise(fib) # <== Memoise magic
system.time(fib(100)) 
#   user  system elapsed 
#   0.02    0.00    0.03