中的R计算使用斐波纳契动态编程

Question

我试着写一个函数来计算第n个斐波纳契数R.我可以递归做到这一点。

fibonacci = function(n){
  if (n == 1) {return(1)}
  if (n == 2) {return(2)}

  return(fibonacci(n - 1) + fibonacci(n - 2))
}

我找不到任何的例子中的R但指南中的其他语言，我想出了以下内容。然而，它似乎并没有跑得更快。

fibonacci = function(n, lookup = NULL){
  if (is.null(lookup)) {
    lookup = integer(n + 1)
  }


  if (n == 1) {return(1)}
  if (n == 2) {return(2)}

  lookup[1] = 1
  lookup[2] = 2

  if (lookup[n - 1] == 0) {
    lookup[n - 1] = fibonacci(n - 1, lookup)
  }

  if (lookup[n - 2] == 0) {
    lookup[n - 2] = fibonacci(n - 2, lookup)
  }
  return(lookup[n - 1] + lookup[n - 2])
}

Answer 1

与您的解决方案的问题是，您的查找矢量总是本地调用帧的环境和新的解决方案不会传播到主叫方，即以查找矢量的变化时，会丢失函数返回。为了使持续的变量在C LA静态变量，您可以创建以充当memoizer功能的属性。这里是一个解决方案：

fibonaccid = function(n, init=T){
  if (init) {
    lookup <- integer(n + 1)
    lookup[1] <- 1
    lookup[2] <- 2
  } else {
    lookup <- attr(fibonaccid, ".lookup")
  }

  # ... calculate lookup as before, recurse with fibonaccid(...,init=F)

  attr(fibonaccid, ".lookup") <<- lookup

  return(lookup[n - 1] + lookup[n - 2])
}

这确实是运行速度更快：

R> system.time(print(fibonacci(35)))
[1] 14930352
   user  system elapsed
  20.923  0.140  21.446

R> system.time(print(fibonaccid(35)))
[1] 14930352
   user  system elapsed
  0.202   0.006   0.209

见this post以获取更多信息。