在计算以某个表达式停止的总和时，控制递归

Question

我想计算[从i = m到n]的[sum（m i）^n]的总和。当N到达M而不是递归达到零时，我该如何停止递归？例如一些输入

Main>Sum 0 1
0
Main>Sum 1 1
1
Main>Sum 0 3
36
Main>Sum 1 5
12200
Main>Sum 3 4
3697

这是我想到的，但是当m = n且结果不正确时，它不起作用。

sum :: Integer->Integer->Integer             
sum m n
|  (m<0 && n <0) = 0
|  n<m =0
|  otherwise = (sum m (n-1)) + ((m+n)^n)

Answer 1

您需要应用

的数学事实

(Sum f(x) from x=n to m) = f(n) + (Sum f(x) from x=n+1 to m) when n < m

和那个

(Sum f(x) from x=m to m) = f(m)

另外，负n或m是错误。让我们将其直接翻译成Haskell：

sum :: (Integer -> Integer) -> Integer -> Integer -> Integer
sum f n m
  | (n < 0 || m < 0) = error "Negative limits"
  -- The first rule above
  | n < m = f n + sum f (n + 1) m
  -- The second rule above
  | n == m = f m

上面的函数是从i到汇总的函数给出的一般求和上的递归。要获取所需的实际功能：

yourFunction :: Integer -> Integer -> Integer
yourFunction n m = sum (i -> (n + i)^m) n m

请注意递归在上面的第一个规则中的工作方式。递归调用 sum f (n + 1) m表示增加 n直到它等于m，加起来所有中间结果。