| title | author | license | tags | summary | layout | src |
|---|---|---|---|---|---|---|
Faster recursion: The Fibonacci sequence |
Dirk Eddelbuettel |
GPL (>= 2) |
recursion function benchmark featured |
This example shows how to call a recursive function |
post |
2012-12-23-fibonacci-sequence.cpp |
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:
{% highlight r %}
fibR <- function(n) { if ((n == 0) | (n == 1)) return(1) else return(fibR(n-1) + fibR(n-2)) }
fibR(20) {% endhighlight %}
[1] 10946
This translates almost literally in C++:
{% highlight cpp %} #include <Rcpp.h>
// [[Rcpp::export]] int fibCpp(int n) { if ((n == 0) | (n == 1)) return 1; else return fibCpp(n-1) + fibCpp(n-2); } {% endhighlight %}
{% highlight r %} fibCpp(20) {% endhighlight %}
[1] 10946
We can time this easily thanks to the rbenchmark package:
{% highlight r %} library(rbenchmark)
benchmark(fibR(20), fibCpp(20))[,1:4] {% endhighlight %}
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++.