CODEWITHSUNDEEP
scalarecursion
user701254
user701254

Reputation: 3953

Understanding the scala substitution model through the use of sumInts method

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.

Upvotes: 4

Views: 1274

Answers (3)

phant0m
phant0m

Reputation: 16905

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.

Upvotes: 5

mishadoff
mishadoff

Reputation: 10789

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.

Upvotes: 6

sepp2k
sepp2k

Reputation: 370407

You mentioned the substitution model, so let's apply it to your sumInts method:

We start by calling sumInts(3,4) (you've used 6 as the second argument, but I chose 4, so I can type less), so let's substitute 3 for a and 4 for b in the definition of sumInts. This gives us:

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

So, what will the result of this be? Well, 3 > 4 is clearly false, so the end result will be equal to the else clause, i.e. 3 plus the result of sumInts(4, 4) (4 being the result of 3+1). Now we need to know what the result of sumInts(4, 4) will be. For that we can substitute again (this time substituting 4 for a and b):

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

Okay, so the result of sumInts(4,4) will be 4 plus the result of sumInts(5,4). So what's sumInts(5,4)? To the substitutionator!

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

This time the if condition is true, so the result of sumInts(5,4) is 0. So now we know that the result of sumInts(4,4) must be 4 + 0 which is 4. And thus the result of sumInts(3,4) must be 3 + 4, which is 7.

Upvotes: 1

Related Questions