algorithm - Why is my recursive function so slow in R?

Question

The following takes about 30 seconds to run whereas I would expect it to be nearly instant. Is there a problem with my code?

x <- fibonacci(35);

fibonacci <- function(seq) {
    if (seq == 1) return(1);
    if (seq == 2) return(2);
    return (fibonacci(seq - 1) + fibonacci(seq - 2));
}

Answer 1

Patrick Burns gives an example in R Inferno of one way to do memoization in R with local() and <<-. In fact, it's a fibonacci:

fibonacci <- local({
    memo <- c(1, 1, rep(NA, 100))
    f <- function(x) {
        if(x == 0) return(0)
        if(x < 0) return(NA)
        if(x > length(memo))
        stop("’x’ too big for implementation")
        if(!is.na(memo[x])) return(memo[x])
        ans <- f(x-2) + f(x-1)
        memo[x] <<- ans
        ans
    }
})