scala - 递归函数溢出，为什么？

Question

下面的函数溢出了，我不明白为什么。当 x 为 0、y 为 0、dim 为 2 运行时，结果应为 6。但是，我收到一个错误，表明函数中的某个 Long 值（x 或 y）在溢出时为 554。这应该是不可能的，因为 x 和 y 都受暗值的限制，在我的测试中设置为 2。这是代码：

def lattice(dim: Long, x: Long, y: Long): Long = { 
  if (x == dim && y == dim) {
    1
  }
  if (x >= dim) {
    lattice(dim,x,y+1L)
  }
  if (y >= dim) {
    lattice(dim,x+1L,y)
  }
  else {
    lattice(dim,x+1L,y) + lattice(dim,x,y+1L)
  }
}

Answer 1

你else在两个地方失踪了。这意味着您的最后一行即使在 时也会运行x >= dim，从而导致 x 超过dim。试试这个：

if (x == dim && y == dim) {
    1
} else if (x >= dim) {
    lattice(dim,x,y+1L)
} else if (y >= dim) {
    lattice(dim,x+1L,y)
} else {
    lattice(dim,x+1L,y) + lattice(dim,x,y+1L)
}

Answer 2

克里斯：

Youd 函数不是尾递归的，因为在你的最后一条语句中你有一个总和。碰巧这个总和涉及两次调用lattice. 但是，要进行尾递归，您的 last statament 必须是一个常量（就像您在 first 中所做的那样if）或只是对函数本身的调用（例如您的 2 else ifs.

我承认我不知道如何将您的函数更改为尾递归。根据您的算法，也许不可能执行您的函数尾递归。

谢谢，

拉斐尔·阿方索