Predictive Hacks

Iteration vs Reduce vs Recursion vs Memoization in R

Today, we are going to introduce and compare some concepts of Functional Programming like “Reduce”, “Recursion” and “Memoization” taking as an example the factorial:

\(n!=n \times (n-1)!=n \times (n-1) \times (n-2) \times … \times1\)

Iteration

Write a function which calculates the factorial of an integer \(n\) using a for loop.

factorial_iteration <- function(x){
  y <- 1
  if(x == 0) return(1)
  for (i in 1:x){
    y <- y*i
  }
  return(y)
}

# test the outcome of factorial(6)
factorial_iteration(6) 
 
[1] 720

Reduce

Write a function which calculates the factorial of an integer \(n\) using the reduce function of purrr package.

library(purrr)
factorial_reduce <- function(x){
  if(x == 0) return(1)
  else{ 
    reduce(as.numeric(c(1:x)), function(x, y){
      x * y
    })
  }
}

# test the outcome of factorial(6)
factorial_reduce(6)
[1] 720

Recursion

Write a function which calculates the factorial of an integer \(n\) using the recursive approach.

factorial_recursive<- function(x) {
    if(x==0) {return(1)}
    else if(x==1) {return(1)}
    else {return(x * factorial_recursive(x-1))}
}
# test the outcome of factorial(6)
factorial_recursive(6)
[1] 720

Recursion with Memoization

First we’ll create a very simple table which is just a vector containing 1 and then 100 NAs. First the factorial_mem () function will check if the number is in the table, and if it is then it is returned. Otherwise the factorial number is recursively calculated and stored in the table. Notice that we’re using the complex assignment operator <<- in order to modify the table outside the scope of the function.

mem_tbl <- c(1, rep(NA, 100))
factorial_mem <- function(x){
  if (x == 0) return(1)
  if(!is.na(mem_tbl[x])) return(mem_tbl[x])
  else{
    mem_tbl[x] <<- x * factorial_mem(x-1)
    return(mem_tbl[x])
  }
}
# test the outcome of factorial(6)
factorial_mem(6)
[1] 720

Comparison of the Performance in terms of Speed

We will use the library microbenchmark in order to compare the performance of these 4 functions. We will consider a relative big number, which is the factorial 100.

library(microbenchmark)
Comparison<- microbenchmark(
                        iteration=factorial_iteration(100),
                        reduce=factorial_reduce(100),
                        recursion=factorial_recursive(100),
                        memoization=factorial_mem(100)
                        )
Comparison
Unit: nanoseconds
        expr    min     lq   mean median     uq     max neval cld
   iteration   4500   5300 104515   9500  10500 9605300   100  a 
      reduce 218600 228450 433508 445050 458750 6820500   100   b
   recursion  59500  61650  86308  69750 108300  145400   100  a 
 memoization    700   1300   2231   1600   3000    6100   100  a 
library(ggplot2)
autoplot(Comparison)
Iteration vs Reduce vs Recursion vs Memoization in R 1

Discussion

It is obvious that the Memoization is much faster compared to the other approaches. Then, the more efficient appears to be the Iteration. Finally, the Reduce seems to be the least efficient in terms of speed.

Share This Post

Share on facebook
Share on linkedin
Share on twitter
Share on email

Leave a Comment

Subscribe To Our Newsletter

Get updates and learn from the best

More To Explore