R:递归太慢 [英] R: recursive too slow

问题描述

我有 R 运行功能:

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

f(50) 需要很长时间来计算.f(35) 大约需要 30 秒.有没有办法让它在R中更快?

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

编辑.感谢帮助！我使用了它，它立即给了我 f(50).

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
+ }
+ })

推荐答案

这是一个递归函数的注释问题，可以通过 尾递归.不幸的是，R 似乎不支持尾调用优化.幸运的是，您总是可以使用迭代解决方案，您应该相当快，因为​​它不必分配堆栈帧:

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)'

此程序在 ideone 上运行约 0.45 秒.我个人不了解 R，程序来源:http://rosettacode.org/wiki/Fibonacci_numbers#R

这篇关于R:递归太慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！