Understanding the scala substitution model through the use of sumInts method

Question

I'm doing a scala course and one of the examples given is the sumInts function which is defined like :

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

I've tried to understand this function better by outputting some values as its being iterated upon :

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
        }
}

So the code :

object SumIntsMain {

    def main(args: Array[String]) {

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

  }

}

Returns the output :

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

Can someone explain how these values are computed. I've tried by outputting all of the created variables but still im confused.

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.

manual-human-tracer off.

Answer 2

To understand what recursive code does, it's not necessary to analyze the recursion tree. In fact, I believe it's often just confusing.

Pretending it works

Let's think about what we're trying to do: We want to sum all integers starting at a until some integer b.

a + sumInts(a + 1 , b)

Let us just pretend that sumInts(a + 1, b) actually does what we want it to: Summing the integers from a + 1 to b. If we accept this as truth, it's quite clear that our function will handle the larger problem, from a to b correctly. Because clearly, all that is missing from the sum is the additional term a, which is simply added. We conclude that it must work correctly.

A foundation: The base case

However, this sumInts() must be built on something: The base case, where no recursion is involved.

if(a > b) 0

Looking closely at our recursive call, we can see that it makes certain assumptions: we expect a to be lower than b. This implies that the sum will look like this: a + (a + 1) + ... + (b - 1) + b. If a is bigger than b, this sum naturally evaluates to 0.

Making sure it works

Seeing that sumInts() always increases a by one in the recursive call guarantees, that we will in fact hit the base case at some point.

Noticing further, that sumInts(b, b) will be called eventually, we can now verify that the code works: Since b is not greater than itself, the second case will be invoked: b + sumInts(b + 1, b). From here, it is obvious that this will evaluate to: b + 0, which means our algorithm works correctly for all values.