Scala:列表上的递归求和

Question

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

任何人都可以解释最后一行.

那么中间结果存储在xs.head + sum(xs.tail)中,+之后是否提供了要添加的单个元素？

Answer 1

解释递归的最佳方法恕我直言是通过逐步完成它来看看实际发生了什么.另一个有用的是添加return语句,特别是如果你来自Java这样的语言,因为它更容易理解发生了什么.

带返回的函数如下所示:

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

在您的情况下,您具有对列表中的所有整数求和的函数.

因此,让我们假设您使用具有以下值的列表调用函数(1,2,3)

功能如何表现？

第一个函数调用将如下所示:

if(xs.isEmpty) // false - it has 3 elements (1,2,3)
   return 0 // skipped
else
   return 1 + sum((2,3)) // xs.head is changed with 1 and xs.tail is list with (2,3)

第二个电话现在是列表(2,3):

if(xs.isEmpty) // false - it has 2 elements (2,3)
   return 0 // skipped
else
   return 2 + sum((3)) // xs.head is changed with 2 and xs.tail is list with (3)

Trird调用现在带有list(3):

if(xs.isEmpty) // false - it has 1 elements (3)
   return 0 // skipped
else
   return 3 + sum(()) // xs.head is changed with 3 and xs.tail is empty list now

第四次调用是空列表:

 if(xs.isEmpty) // true
    return 0 // Recursion termination case triggered

所以现在我们的sum调用栈看起来像这样:

sum((1,2,3))   
   where sum = 1 + sum((2,3))   
       where sum = 2 + sum((3))   
          where sum = 3 + sum(())    
             where sum = 0

我们只是开始返回值:

sum((1,2,3))   
       where sum = 1 + 5   
           where sum = 2 + 3  
              where sum = 3 + 0 

所以我们最终得到总和((1,2,3))= 6

这就是为什么我们不需要存储"中间结果",因为计算总和从结束开始并向后滚动.