Understanding the scala lookup model using the sumInts method

Question

I am doing a scala course, and one of the above examples is the sumInts function, which is defined as:

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

I tried to better understand this function by outputting some values ​​as it repeats:

 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 calculated. I tried to output all the created variables, but still got confused.

Answer 1

manual-human-tracer:

 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.

Answer 2

To understand what recursive code does, there is no need to parse the recursion tree. In fact, I find this often just confusing.

Pretending to be working

Think about what we are trying to do: we want to sum all the integers starting from a to some integer b .

a + sumInts (a + 1, b)

Let's just pretend that sumInts(a + 1, b) really does what we want: summing integers from a + 1 to b . If we accept this as true, then it is very clear that our function will handle the big problem, from a to b correctly. Because, obviously, everything that is absent in the sum is an additional term a , which is simply added. We conclude that it should work correctly.

Base: base case

However, this sumInts() must be built on something: a base register in which recursion is not involved.

if (a> b) 0

Looking carefully at our recursive call, we see that he makes certain assumptions: we expect a be lower than b . This means that the sum will look like this: a + (a + 1) + ... + (b - 1) + b . If a greater than b , this sum is naturally 0.

Make sure it works

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

Noting further that sumInts(b, b) will be called in the end, we can now check whether the code works: since b not larger than itself, the second case will be called: b + sumInts(b + 1, b) . From here it is obvious that this will be evaluated as: b + 0 , which means that our algorithm works correctly for all values.

Answer 3

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

Let's start by calling sumInts(3,4) (you used 6 as the second argument, but I chose 4, so I can print less), so replace 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 be the result of this? Well, 3 > 4 clearly false, so the final result will be equal to the else condition, i.e. 3 plus the result of sumInts(4, 4) (4 - the result of 3+1 ). Now we need to know what the result of sumInts(4, 4) . To do this, we can replace again (this time substituting 4 for a and b ):

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

Ok, so the result of sumInts(4,4) will be 4 plus the result of sumInts(5,4) . So what is sumInts(5,4) ? To the substitute!

 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, therefore, the result of sumInts(3,4) should be 3 + 4 , which is equal to 7.