Faster recursion: The Fibonacci sequence

Dirk Eddelbuettel — written 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

Extending R with C++ and Fortran — Dirk Eddelbuettel and JBrandon Duck-Mayr
Benchmarking Rcpp code with RcppClock — Zach DeBruine
Simulation Smoother using RcppArmadillo — Tomasz Woźniak

Faster recursion: The Fibonacci sequence

Related Articles