R 中的斐波那契记忆

Question

我正在尝试在 R 中使用递归记忆化实现斐波那契数列。我对 R 有基本的想法并尝试使用它们来实现。

这是我试过的代码（不工作）。

    rm(list = ls())   ##Clearing Environment
    ##Fibonacci_using Recursion
    fibvals <<- numeric(3)
    fibvals[1:length(fibvals)] <- NA
    fib_recursive <- function(n){
        if(is.na(fibvals[n])){ 
            if (n == 1) {
                fibvals[n] <- 0
                return(0)
            } 
            if (n == 2){
                fibvals[1] <- 0
                fibvals[n] <- 1
                return(1)
            } 
        fibvals[n] <- (fib_recursive(n - 1) + fib_recursive(n - 2)) 
        }
        return(fibvals)
    }
    fib_recursive(5)

能否请您提出更正和改进建议。谢谢

Answer 1

递归变体，但没有记忆会是这样的：

int fibonnaci(int n) {
    if(n == 1 || n == 2)
       return 1;
    return fibonnaci(n-1) + fibonnaci(n-2);
}

显然，此代码经常重新进行相同的计算。您必须将值存储在一个数组中，代码看起来像这样

int fibonnaci(int n) {
    if(a[n]==0)
       a[n]=fibonnaci(n-1) + fibonnaci(n-2);
    return a[n];
}

此外，不要忘记 a[MAXN] = {1, 1} 字符串的前两个元素。

R 中的斐波那契记忆

Fibonacci Memoization in R

r

fibonacci

memoization