Dirk Eddelbuettel — Dec 23, 2012 | source

A StackOverflow post
once put the question directly in its title: *Why is my recursive function so slow in R?*

To cut a long story short, function calls are among the less performing parts of the R language. Operating on objects and the language itself gives us very powerful features, but the required state and stack checking for function calls is one of the prices we pay.

And as the Fibonacci sequence has such a simple definition, the simple R program can be translated easily giving us a nice example for the power of C++ particularly for function evaluations.

All that said, real computer scientists do of course insist that one should not call the sequence recursively. See for example the this post; memoization approaches are easy in R too.

Let us start with the R function:

```
## create M as a sum of two outer products
fibR <- function(n) {
if ((n == 0) | (n == 1))
return(1)
else
return(fibR(n-1) + fibR(n-2))
}
fibR(20)
```

[1] 10946

This translates almost literally in C++:

```
#include <Rcpp.h>
// [[Rcpp::export]]
int fibCpp(int n) {
if ((n == 0) | (n == 1))
return 1;
else
return fibCpp(n-1) + fibCpp(n-2);
}
```

`fibCpp(20)`

[1] 10946

We can time this easily thanks to the rbenchmark package:

```
library(rbenchmark)
benchmark(fibR(20), fibCpp(20))[,1:4]
```

test replications elapsed relative 2 fibCpp(20) 100 0.008 1 1 fibR(20) 100 8.591 1074

This demonstrates a rather tangible speed gain illustrating that function calls can indeed be expensive. As for the Fibonacci sequence, non-recursive approaches can of course be used to provide a speedier implementation in either R or C++.

**tags:**
recursion
function
benchmark

- Create an R-tree data structure using Rcpp and Boost::Geometry — teramonagi and Dirk Eddelbuettel
- Sampling Importance Resampling (SIR) and social revolution. — Jonathan Olmsted
- Implementing an EM Algorithm for Probit Regressions — Jonathan Olmsted