为什么我的递归函数在 R 中这么慢? [英] Why is my recursive function so slow in R?

问题描述

以下运行大约需要 30 秒，而我希望它几乎是即时的.我的代码有问题吗?

The following takes about 30 seconds to run whereas I would expect it to be nearly instant. Is there a problem with my code?

x <- fibonacci(35);

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

推荐答案

Patrick Burns 在 R 中给出了一个例子在 R 中使用 local() 和 <<- 进行记忆的一种方法的地狱.事实上，这是一个斐波那契:

Patrick Burns gives an example in R Inferno of one way to do memoization in R with local() and <<-. In fact, it's a fibonacci:

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

这篇关于为什么我的递归函数在 R 中这么慢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！