R语言递归函数计算值是否默认存储？如何实现缓存优化？

背景与问题 #

我使用Mathematica已有多年，刚开始用R语言进行编程。两者均支持定义递归函数，Mathematica中可实现函数值存储，但不确定R是否默认支持。以斐波那契数列为例：

Mathematica中初始定义：

fibonacci[0]=1;
fibonacci[1]=1;
fibonacci[n_]:=fibonacci[n-1]+fibonacci[n-2];

计算fibonacci[10]时需先求出i=2至9的所有fibonacci[i]，后续计算fibonacci[11]时需重复计算i=2至10的所有值，未存储已得结果。修改后的Mathematica代码可实现存储：

fibonacci[0]=1;
fibonacci[1]=1;
fibonacci[n_]:=fibonacci[n]=fibonacci[n-1]+fibonacci[n-2];

此方式下计算fibonacci[10]后会存储该值，后续计算fibonacci[11]无需重复计算，可大幅提升大数值（如fibonacci[10^9]）的计算效率。

R语言中斐波那契函数的初始定义如下：

fibonacci = function(n) { 
    if (n==0 | n==1) { n } 
    else {fibonacci(n-1)+fibonacci(n-2)}}

提问 #

1. R语言计算fibonacci(10)后是否会存储该值？计算fibonacci(11)时是否会重复计算fibonacci(10)？
2. 补充：计算fibonacci(30)（值为832040）和fibonacci(31)（值为1346269）时，发现fibonacci(31)耗时更长，说明上述R函数未存储中间值。请问如何修改代码使R能存储递归函数的中间值？

问题解答 #

1. 原R函数的结果存储情况 #

原定义的递归斐波那契函数不会自动存储任何已计算的结果。每次调用fibonacci(n)时，都会从头递归计算所有依赖的子项：

• 计算fibonacci(10)后，不会保留fibonacci(10)或任何中间值；
• 计算fibonacci(11)时，会重新完整计算fibonacci(10)以及所有更小的项，这也是fibonacci(31)比fibonacci(30)耗时显著更长的核心原因。

2. 实现递归函数结果缓存的方法 #

在R中实现递归函数的结果缓存（即记忆化），有三种常用方案：

方案一：手动用环境管理缓存

利用R的环境特性，创建一个专门存储已计算值的缓存环境，手动管理结果的存储与读取：

fibonacci <- function() {
    # 创建缓存环境
    cache <- new.env(hash = TRUE)
    # 初始化基础值
    cache$`0` <- 0
    cache$`1` <- 1
    
    # 定义带缓存的递归函数
    f <- function(n) {
        n_char <- as.character(n)
        if (n_char %in% ls(cache)) {
            return(cache[[n_char]])
        }
        # 计算并存储结果到缓存
        result <- f(n-1) + f(n-2)
        cache[[n_char]] <- result
        result
    }
    f
}

# 初始化带缓存的函数实例
fib <- fibonacci()

# 调用示例
fib(10)  # 首次计算后，所有中间值都会被缓存
fib(11)  # 直接读取缓存的fib(10)和fib(9)，无需重复计算

方案二：使用memoise包快速实现记忆化

R的memoise包封装了记忆化逻辑，无需手动管理缓存，使用更简洁：

# 先安装并加载包
install.packages("memoise")
library(memoise)

# 原递归函数
fibonacci <- function(n) {
    if (n == 0 | n == 1) {
        n
    } else {
        fibonacci(n-1) + fibonacci(n-2)
    }
}

# 将原函数包装成带缓存的版本
fib <- memoise(fibonacci)

# 调用示例
fib(30)  # 首次计算会缓存所有中间值
fib(31)  # 直接使用缓存的fib(30)和fib(29)，计算速度大幅提升

方案三：迭代实现（高效替代递归）

如果追求极致效率，迭代实现的斐波那契函数天然避免了重复计算，还能规避递归的栈开销，适合计算超大n值：

fibonacci <- function(n) {
    if (n == 0) return(0)
    if (n == 1) return(1)
    a <- 0
    b <- 1
    for (i in 2:n) {
        temp <- b
        b <- a + b
        a <- temp
    }
    b
}

# 调用示例
fibonacci(100000)  # 高效计算，无重复计算开销

内容的提问来源于stack exchange，提问作者Pengfei