2

我是Scala新手，开始学习尾递归。我了解到函数式编程中的尾递归是命令式编程中迭代（for循环）的对应部分：

对列表元素求和的简单 C++ 循环：

uint32_t sum = 0;
for (size_t i = 0; i < list.length(); ++i) {
    sum += list[i];
}

Scala递归等价物：

def listSum(list: List[Int]): Int = {
  def listSumHelper(list: List[Int], sum: Int): Int = {
    if (list.isEmpty) sum
    else listSumHelper(list.tail, sum + list.head)
  }
  listSumHelper(list, 0)
}

问题： 嵌套 for 循环的 scala 递归等价物是什么？

uint32_t sum = 0;
for (size_t i = 0; i < list.width(); ++i) {
    for (size_t j = j < list.height(); ++j) {
        sum += list[i][j];
    }
}
4

2 回答 2

2

只需编写一个适用于嵌套列表 ( List[List[Int]]) 的相同列表递归方法：

def listSum2(list: List[List[Int]]): Int = {
  @tailrec def listSumHelper2(list: List[List[Int]], sum: Int): Int = {
    if (list.isEmpty) sum
    else listSumHelper2(list.tail, sum + listSum(list.head))
  }
  listSumHelper2(list, 0)
}
于 2013-03-28T15:49:14.833 回答
2

如果您想要完全尾递归，您应该将所有循环移动到参数中。所以（这里没有帮助，只是为了简洁）：

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

但是你可能不需要它，除非你的循环真的很短；每次迭代只需一个尾递归函数调用另一个。

于 2013-03-28T16:45:46.417 回答