为什么我的递归函数在R中这么慢？

一尘不染

为什么我的递归函数在R中这么慢？

algorithm

接下来的过程大约需要30秒，而我希望它几乎是即时的。我的代码有问题吗？

x <- fibonacci(35);

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

阅读 255

2020-07-28

共1个答案

一尘不染

帕特里克·伯恩斯（Patrick Burns）在R Inferno中举例说明了一种使用local()和进行R中记忆的方法<<-。实际上，这是斐波那契：

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

2020-07-28