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)
[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
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 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.
