递归求和函数，我如何限制总和？

Question

目标是将这个总和编码成一个递归函数。 Sum

到目前为止我已经试过这样编码了。

def under(u: Int): Int = {
    var i1 = u/2
    var i = i1+1
    if (  u/2 == 1 ) then u + 1 - 2 * 1
    else   (u + 1 - 2 * i) + under(u-1)
}

我似乎运行遇到了递归部分的问题，但我无法弄清楚哪里出了问题。理论上，under(5) 应该产生 10。

Answer 1

你的逻辑是错误的。它应该从 i=1 迭代到 i=n/2（无论是通过循环、递归还是收集都无关紧要）。但按原样使用 n 和当前 i。

(1 to (n/2)).map(i => n + 1 - 2 * i).sum

你（或多或少）运行计算从 i=1 到 i=n（或者更确切地说 n 下降到 1）但是你使用 [=而不是 n 20=] 而不是 i 你使用 i/2+1。（从 i=1 到 i=n 的 (n/2 + 1 - 2 * i) 的和）。

// actually what you do is more like (1 to n).toList.reverse
// rather than (1 to n)
(1 to n).map(i => i/2 + 1 - 2 * (i/2 + 1)).sum

这是一个不同的公式。它有两倍的元素要求和，每个元素的一部分都在变化而不是不变，而另一部分的值是错误的。

要通过递归实现相同的逻辑，您必须执行如下操作：

// as one function with default args

// tail recursive version
def under(n: Int, i: Int = 1, sum: Int = 0): Int =
  if (i > n/2) sum
  else under(n, i+1, sum + (n + 2 - 2 * i))

// not tail recursive
def under(n: Int, i: Int = 1): Int =
  if (i > n/2) 0
  else (n + 2 - 2 * i) + under(n, i + 1)

// with nested functions without default args

def under(n: Int): Int = {
  // tail recursive
  def helper(i: Int, sum: Int): Int =
    if (i > n/2) sum
    else helper(i + 1, sum + (n + 2 - 2 * i))
  helper(1, 0)
}

def under(n: Int): Int = {
  // not tail recursive
  def helper(i: Int): Int =
    if (i > n/2) 0
    else (n + 2 - 2 * i) + helper(i + 1)
  helper(1)
}

Answer 2

附带说明：根本不需要使用任何迭代/递归。这是一个明确的公式：

def g(n: Int) = n / 2 * (n - n / 2)

给出与

相同的结果

def h(n: Int) = (1 to n / 2).map(i => n + 1 - 2 * i).sum

在 n 为奇数的情况下，两者都假设您想要 floored n / 2，即以上两个函数的行为与

相同

def j(n: Int) = (math.ceil(n / 2.0) * math.floor(n / 2.0)).toInt

（至少在出现舍入错误之前）。

递归求和函数，我如何限制总和？

Recursive sum function, How do i limit the sum?

recursion

functional-programming

scala