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)

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