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

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


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


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?

>Solution :

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)
    fib(i - 1) + fib(i - 2)
#   user  system elapsed 
#   0.92    0.00    1.84 
fib <- memoise(fib) # <== Memoise magic
#   user  system elapsed 
#   0.02    0.00    0.03 

Leave a Reply