improve `fib()` in R

[kadyb]

I propose to improve the fib() function in R using vector preallocation. This is standard practice in R, and speeds up by more than 500 times compared to the current version.

library("microbenchmark")

fib_new = function(n) {
  if (n < 2) return(n)
  if (n == 2) return(1)
  k = integer(n)
  k[1:2] = c(1L, 1L)
  for (i in 3:n) k[i] = k[i - 1] + k[i - 2]
  return(k[n])
}

# current version
fib = function(n) {
  if (n < 2) {
    return(n)
  } else {
    return(fib(n-1) + fib(n-2))
  }
}

microbenchmark(fib_new(20), fib(20), check = "equal")
#> Unit: microseconds
#>         expr       min        lq       mean     median         uq       max
#>  fib_new(20)    87.032    90.727   113.2529   108.7905   132.8065   173.654
#>      fib(20) 61421.569 62131.371 64658.5869 62758.8640 64157.9440 95407.957

[ChrisRackauckas]

fib_recursion is a test of recursion speeds. Your algorithm is not using recursion, so it's not a test of recursion speeds.

[kadyb]

Thanks for the clarification! I will close this PR then.