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 that 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)


 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)

 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)

 720


## Recursion with Memoization

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)

 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 relatively 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)


## 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.