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

Question

目标是将此总和编码为递归函数。 和

到目前为止，我已经尝试像这样编码。

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而是使用i/2而不是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奇数的情况下进行地板n / 2，即上述两个函数的行为与

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

(至少在舍入错误开始之前)。