4

我正在学习 Scala 课程，给出的示例之一是 sumInts 函数，其定义如下：

  def sumInts(a: Int, b: Int) : Int = 
    if(a > b) 0  
    else a + sumInts(a + 1 , b)

我试图通过在迭代时输出一些值来更好地理解这个函数：

class SumInts {
      def sumInts(a: Int, b: Int) : Int = 
        if(a > b) 0 else 
        {     
          println(a + " + sumInts("+(a + 1)+" , "+b+")")       
          val res1 = sumInts(a + 1 , b)
          val res2 = a
          val res3 = res1 + res2
          println("res1 is : "+res1+", res2 is "+res2+", res3 is "+res3)
          res3
        }
}

所以代码：

object SumIntsMain {

    def main(args: Array[String]) {

      println(new SumInts().sumInts(3 , 6));

  }

}

返回输出：

3 + sumInts(4 , 6)
4 + sumInts(5 , 6)
5 + sumInts(6 , 6)
6 + sumInts(7 , 6)
res1 is : 0, res2 is 6, res3 is 6
res1 is : 6, res2 is 5, res3 is 11
res1 is : 11, res2 is 4, res3 is 15
res1 is : 15, res2 is 3, res3 is 18
18

有人可以解释如何计算这些值。我已经尝试输出所有创建的变量，但我仍然感到困惑。

4

3 回答 3

6

手动人类追踪器：

return sumInts(3, 6) | a = 3, b = 6
3 > 6 ? NO
return 3 + sumInts(3 + 1, 6) | a = 4, b = 6
4 > 6 ? NO
return 3 + (4 + sumInts(4 + 1, 6)) | a = 5, b = 6
5 > 6 ? NO
return 3 + (4 + (5 + sumInts(5 + 1, 6))) | a = 6, b = 6
6 > 6 ? NO
return 3 + (4 + (5 + (6 + sumInts(6 + 1, 6)))) | a = 7, b = 6
7 > 6 ? YEEEEES (return 0)
return 3 + (4 + (5 + (6 + 0))) = return 18.

手动人类追踪器关闭。

于 2012-09-26T16:06:22.633 回答
5

要了解递归代码的作用，无需分析递归树。事实上，我相信这往往只是令人困惑。

假装它有效

让我们考虑一下我们正在尝试做的事情：我们想要对从开始的所有整数求和，a直到某个整数b。

a + sumInts(a + 1 , b)

让我们假装它sumInts(a + 1, b)确实做了我们想要的：对从a + 1到的整数求和b。如果我们接受这是事实，很明显我们的函数将处理更大的问题，从正确a到b正确。因为很明显，总和中缺少的只是附加项a，它只是简单地相加。我们得出结论，它必须正常工作。

基础：基础情况

但是，这sumInts()必须建立在某些东西之上：基本情况，其中不涉及递归。

如果(a > b) 0

仔细观察我们的递归调用，我们可以看到它做出了某些假设：我们期望a低于b. 这意味着总和将如下所示 a + (a + 1) + ... + (b - 1) + b：如果a大于b，这个和自然地计算为 0。

确保它有效

看到在递归调用保证中sumInts()总是加a一，我们实际上会在某个时候达到基本情况。

进一步注意，sumInts(b, b)最终将调用它，我们现在可以验证代码是否有效：由于b不大于自身，因此将调用第二种情况b + sumInts(b + 1, b)：从这里，很明显这将评估为：b + 0，这意味着我们的算法对所有值都正确工作。

于 2012-09-26T16:41:04.347 回答
1

您提到了替换模型，所以让我们将其应用于您的sumInts方法：

我们首先调用sumInts(3,4)（你使用 6 作为第二个参数，但我选择了 4，所以我可以输入更少），所以让我们在定义中用 3a和 4替换. 这给了我们：bsumInts

if(3 > 4) 0  
else 3 + sumInts(3 + 1, 4)

那么，这会是什么结果呢？好吧，3 > 4显然是错误的，所以最终结果将等于 else 子句，即 3 加上sumInts(4, 4)（4 是3+1）的结果。现在我们需要知道sumInts(4, 4)will 的结果是什么。为此，我们可以再次替换（这次用 4 替换aand b）：

if(4 > 4) 0
else 4 + sumInts(4 + 1, 4)

好的，所以 的结果sumInts(4,4)将是 4 加上 的结果sumInts(5,4)。那是什么sumInts(5,4)？给替代者！

if(5 > 4) 0
else 5 + sumInts(5 + 1, 4)

这次 if 条件为真，所以 的结果sumInts(5,4)是 0。所以现在我们知道sumInts(4,4)must be的结果4 + 0是 4。因此sumInts(3,4)must be的结果3 + 4是 7。

于 2012-09-26T16:04:07.937 回答