54

我正在尝试编写一个 scala 函数，它将递归地对列表中的值求和。这是我到目前为止所拥有的：

  def sum(xs: List[Int]): Int = {
    val num = List(xs.head)   
    if(!xs.isEmpty) {
      sum(xs.tail)
    }
    0
   }

我不知道如何将各个 Int 值求和作为函数的一部分。我正在考虑在函数 sum 中定义一个新函数，并使用一个局部变量来对 List 迭代时的值求和。但这似乎是一种势在必行的方法。有替代方法吗？

4

12 回答 12

111

你也可以避免直接使用递归，而是使用一些基本的抽象：

val l = List(1, 3, 5, 11, -1, -3, -5)
l.foldLeft(0)(_ + _) // same as l.foldLeft(0)((a,b) => a + b)

foldLeft就像reduce()在python中一样。还有foldRight一个也称为accumulate（例如在 SICP 中）。

于 2012-10-13T14:21:08.053 回答
80

对于递归，我经常发现值得考虑如何用英语描述该过程，因为这通常可以转化为没有太多复杂性的代码。所以...

“如何递归计算整数列表的总和？”

“嗯，一份清单的总和是多少，3 :: restOfList？

“什么restOfList？

“它可以是任何东西，你不知道。但请记住，我们是递归的——你没有计算列表总和的函数吗？”

“哦，对了！那么总和就是3 + sum(restOfList)。

“没错。但现在你唯一的问题是每个总和都是根据另一个调用定义sum()的，并且您可以为其提供价值。”

“嗯，你说得对。” 认为...

“嗯，既然你的名单越来越短，那么最短的名单是多少？”

“空单？”

“对！空的整数列表的总和是多少？”

“零——我现在明白了。所以把它放在一起，一个空列表的总和为零，任何其他列表的总和是它的第一个元素添加到其余列表的总和中。

事实上，这段代码读起来几乎和最后一句话一模一样：

def sumList(xs: List[Int]) = {
    if (xs.isEmpty) 0
    else xs.head + sumList(xs.tail)
}

（模式匹配版本，例如 Kim Stebel 提出的版本，基本上与此相同，它们只是以更“功能性”的方式表达条件。）

于 2012-09-19T14:50:07.587 回答
65

这是“标准”递归方法：

def sum(xs: List[Int]): Int = {
  xs match {
    case x :: tail => x + sum(tail) // if there is an element, add it to the sum of the tail
    case Nil => 0 // if there are no elements, then the sum is 0
  }
}

而且，这是一个尾递归函数。它将比非尾递归函数更有效，因为编译器将其转换为 while 循环，不需要为每次递归调用在堆栈上推入新帧：

def sum(xs: List[Int]): Int = {
  @tailrec
  def inner(xs: List[Int], accum: Int): Int = {
    xs match {
      case x :: tail => inner(tail, accum + x)
      case Nil => accum
    }
  }
  inner(xs, 0)
}
于 2012-09-19T14:36:42.947 回答
40

你不能让它更容易：

val list  = List(3, 4, 12);
println(list.sum); // result will be 19

希望能帮助到你 ：）

于 2015-10-20T19:50:17.520 回答
14

您的代码很好，但您不需要临时值 num。在 Scala 中 [If] 是一个表达式并返回一个值，这将作为 sum 函数的值返回。所以你的代码将被重构为：

def sum(xs: List[Int]): Int = {
    if(xs.isEmpty) 0
    else xs.head + sum(xs.tail)

}

如果列表为空，则返回 0，否则将列表的其余部分添加到头部编号

于 2012-09-19T15:21:02.607 回答
5

具有模式匹配的规范实现：

def sum(xs:List[Int]) = xs match {
  case Nil => 0
  case x::xs => x + sum(xs)
}

这不是尾递归，但很容易理解。

于 2012-09-19T14:37:46.390 回答
3

以@Kim 的回答为基础：

def sum(xs: List[Int]): Int = {
    if (xs.isEmpty) throw new IllegalArgumentException("Empty list provided for sum operation")
    def inner(xs: List[Int]): Int = {
      xs match {
        case Nil => 0
        case x :: tail => xs.head + inner(xs.tail)
      }
    }
    return inner(xs)
  }

内部函数是递归的，当提供空列表时会引发适当的异常。

于 2016-10-17T20:18:03.837 回答
3

如果您需要使用 isEmpty、head 和 tail 编写递归函数，并且在空列表参数的情况下也抛出异常：

def sum(xs: List[Int]): Int = 
  if (xs.isEmpty) throw new IllegalArgumentException("sum of empty list") 
  else if (xs.tail.isEmpty) xs.head 
  else xs.head + sum(xs.tail)
于 2017-05-23T20:54:10.207 回答
1 
 def sum(xs: List[Int]): Int = { 
  def loop(accum: Int, xs: List[Int]): Int = { 
    if (xs.isEmpty) accum
    else loop(accum + xs.head, xs.tail)
  }
  loop(0,xs)  
}
于 2016-08-18T08:10:30.803 回答
1

要为此添加另一个可能的答案，这是我想出的一个解决方案，它与@jgaw 的答案略有不同，并使用了@tailrec注释：

def sum(xs: List[Int]): Int = {
  if (xs.isEmpty) throw new Exception // May want to tailor this to either some sort of case class or do something else

  @tailrec
  def go(l: List[Int], acc: Int): Int = {
    if (l.tail == Nil) l.head + acc // If the current 'list' (current element in xs) does not have a tail (no more elements after), then we reached the end of the list.
    else go(l.tail, l.head + acc) // Iterate to the next, add on the current accumulation
  }

  go(xs, 0)
}

关于检查传入的空列表的快速说明；在进行函数式编程时，最好不要抛出任何异常，而是返回其他内容（另一个值、函数、案例类等）以优雅地处理错误并继续在执行路径中流动，而不是通过Exception. 我在上面的示例中扔了一个，因为我们只是在查看递归地对列表中的项目求和。

于 2017-04-22T14:25:49.547 回答
1 
def sum(xs: List[Int]): Int = xs.sum

scala> sum(List(1,3,7,5))
res1: Int = 16

scala> sum(List())
res2: Int = 0
于 2017-05-29T07:03:57.263 回答
0

在不使用替换方法的情况下尝试了以下方法

def sum(xs: List[Int]) = {

  val listSize = xs.size

  def loop(a:Int,b:Int):Int={

    if(a==0||xs.isEmpty)
      b
    else
      loop(a-1,xs(a-1)+b)
  }

  loop(listSize,0)
}
于 2016-11-25T07:39:15.543 回答