R: recursive too slow

Question

I have R running function:

f <- function (n) {
if ( n == 1) return (0)
if ( n == 2) return (1)
else return ( f(n-1) + f(n-2))
}

f(50) takes very long time to calculate. f(35) takes approx 30 seconds. Is there any way to make it faster in R?

Edit. Thanks for help! I used this and it gave me f(50) instantly.

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

http://gallery.rcpp.org/articles/fibonacci-sequence/ which also links [The worst algorithm in the world?](https://bosker.wordpress.com/2011/04/29/the-worst-algorithm-in-the-world/) — Roland, Oct 31 '15 at 15:04
Yes, by storing your results in a lookuptable. That way you won't compute every number twice. The timecomplexity of the fibonacci however will stay O(n^2) — xXliolauXx, Oct 31 '15 at 15:08
Thanks for help eveyryone! I used this and it did gave me f(50) = 7778742049 instantly. — Mikoyan, Oct 31 '15 at 15:19

score 1 · Answer 1 · answered Oct 31 '15 at 15:06

This is a comment problem with recursive functions that can be solved by tail-recursion. Unfortunately, it appears that R does not support tail call optimization. Fortunately, you can always use the iterative solution, which you should be fairly fast since it does not have to allocate stack frames:

fIter <- function(n) {
  if ( n < 2 )
    n
  else {
    f <- c(0, 1)
    for (i in 2:n) {
      t <- f[2]
      f[2] <- sum(f)
      f[1] <- t
    }
    f[2]
  }
}
fIter(100)'

This program runs in ~0.45 seconds on ideone. I don't know R personally, source of program: http://rosettacode.org/wiki/Fibonacci_numbers#R

R: recursive too slow

1 Answers1

Linked