R中递归解决方案的迭代

Question

我在 R 语言中得到一个问题，要求找到递归关系 x(n) = 2*x(n-1) - x(n-2) 的第 30 项，其中 x(1) = 0 和 x(2) = 1。我从数学推导中知道答案是 29。但作为 R 的新手，我对如何在这里工作感到有些困惑。以下是我的代码：

loop <- function(n){
  a <- 0
  b <- 1
  for (i in 1:30){
    a <- b
    b <- 2*b - a
  }
  return(a)
}

loop(30)

结果我返回了 1，这太离谱了。

如果您想知道为什么这看起来 Python-ish，到目前为止，我基本上只接触过 Python 编程（我是编程新手）。我试图检查 R 中的所有语法，但我想我的逻辑已被 Python 完全固定。在这种情况下有人可以帮我吗？另外，R有没有像PythonTutor这样的资源来帮助可视化代码执行逻辑？

谢谢！

Answer 1

您没有使用在循环中迭代的变量，因此没有任何更新。


loop <- function(n){
  a <- 0
  b <- 1
  for (i in 1:30){
    a <- b
    b <- 2*i - a
  }
  return(a)
}

Answer 2

你可以定义一个递归函数。

f <- function(x, n) {
  n <- 1:n
  r <- function(n) {
    if (length(n) == 2) x[2]
    else r({
      x <<- c(x[2], 2*x[2] - x[1])
      n[-1]
    })
  }
  r(n)
}

x <- c(0, 1)
f(x, 30)
# [1] 29

Answer 3

我猜你需要的可能是下面这样的东西

loop <- function(n){
  if (n<=2) return(n-1)
  a <- 0
  b <- 1
  for (i in 3:n){
    a_new <- b
    b <- 2*b - a
    a <- a_new
  }
  return(b)
}

然后

> loop(30)
[1] 29

如果你需要一个递归版本，下面是一个实现

loop <- function(n) {
  if (n<=2) return(n-1)
  2*loop(n-1)-loop(n-2)
}

这也给出了

> loop(30)
[1] 29

Answer 4

你可以用另外两种方法解决它。

求解线性齐次递推关系，设

x(n) = r^n

代入递推关系，得到二次方程

r^n-2*r^(n-1)+r^(n-2) = 0

，即

r^2-2*r+1=0

，即

r = 1, 1

导致通用解决方案

x(n) = c1 * 1^n + c2 * n * 1^n = c1 + n * c2

并且 x(1) = 0 和 x(2) = 1，你得到 c2 = 1, c1 = -1, s.t.,

x(n) = n - 1

=> x(30) = 29

因此，将 x(n) 计算为 n 的函数的 R 代码很简单，如下所示：

x <- function(n) {
   return (n-1)
}
x(30)
#29

使用矩阵的幂（先从递归关系求出如下矩阵A）：

(矩阵A具有代数/几何重数，其对应的特征向量矩阵是奇异的，否则可以自己使用谱分解来快速计算矩阵的幂，这里我们将使用库expm，如下所示)

library(expm)

A <- matrix(c(2,1,-1,0), nrow=2)

A %^% 29 %*% c(1,0)  # [x(31) x(30)]T = A^29.[x(2) x(1)]T
#      [,1]
# [1,]   30  # x(31)
# [2,]   29  # x(30)

# compute x(n)
x <- function(n) {
    (A %^% (n-1) %*% c(1,0))[2]
}
x(30)
# 29

R中递归解决方案的迭代

Iteration of a recurrence solution in R

r

matrix

iteration

linear-algebra

recurrence