递归R函数与Python实现行为差异原因分析

R语言实现及运行结果 #

f <- function(m, k, n) {
  if(n == 0) {
    return(100)
  }
  if(m == 1) {
    return(0)
  }
  if(!is.na(S[m, n])) {
    return(S[m, n])
  }
  s <- f(m-1, 1, n)
  i <- k
  while(i <= 5) {
    if(n > 2) {
      s <- s + f(m, i, n-1)
    } else {
      s <- s + f(m-1, 1, n-1)
    }
    i <- i + 1
  }
  if(k == 1) {
    S[m, n] <- s
  }
  return(s)
}

运行结果：

> n <- 4
> S <- matrix(NA_real_, nrow = n, ncol = n)
> f(n, 1, n)
[1] 127500

Python语言初始实现及运行结果 #

import numpy as np
def f(m, k, n):
  if n == 0:
    return 100
  if m == 1:
    return 0
  if S[m-1, n-1] is not None: 
    return S[m-1, n-1]
  s = f(m-1, 1, n)
  i = k
  while i <= 5:
    if n > 2:
      s = s + f(m, i, n-1)
    else:
      s = s + f(m-1, 1, n-1)
    i = i + 1
  if k == 1:
    S[m-1, n-1] = s
  return s

运行结果：

>>> n = 4
>>> S = np.full((n, n), None)
>>> f(n, 1, n)
312500

结果不一致的核心原因 #

两者结果差异的根源在于缓存读取的逻辑匹配问题：

• R代码逻辑：仅当k == 1时，才会将计算结果写入缓存矩阵S[m, n]；当k ≠ 1时，调用f(m, k, n)时S[m, n]始终为NA，因此会执行完整递归计算，得到对应k值的正确结果。
• 初始Python代码逻辑：缓存读取不区分k值——当k ≠ 1时调用f(m, k, n)，如果之前k=1的调用已经将结果写入S[m-1, n-1]（Python采用0索引），会直接返回k=1时的缓存值，而非重新计算k≠1对应的结果。这会导致递归累加过程中使用错误数值，最终结果偏大。

将Python代码中的缓存读取判断修改为if k == 1 and S[m-1, n-1] is not None:后，逻辑与R完全对齐：仅当k=1时读取缓存，k≠1时强制重新计算对应结果，因此运行结果与R一致。

内容的提问来源于stack exchange，提问作者Stéphane Laurent