通过使用sumInts方法了解scala替换模型

Question

我正在做一个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

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

Answer 1

manual-human-tracer on:

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.

手动 - 人类追踪器关闭.

Answer 2

要理解递归代码的作用,不必分析递归树.事实上,我认为这通常只是令人困惑.

假装它有效

让我们考虑一下我们要做的事情:我们希望将所有整数加起来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()总是增加a1,我们实际上会在某个时刻触及基本情况.

进一步注意到,sumInts(b, b)最终会调用,我们现在可以验证代码是否正常工作:由于b不大于自身,所以将调用第二种情况:b + sumInts(b + 1, b).从这里开始,很明显这将评估为:b + 0,这意味着我们的算法可以正确地适用于所有值.