def sum(xs: List[Int]): Int = {
if(xs.isEmpty)
0
else
xs.head + sum(xs.tail)
}
Can anyone please explain the last line.
So where is the intermediate result being stored in xs.head + sum(xs.tail) and after the + is it providing a single element to be added?
The best way to explain recursion IMHO is to do it by going through it step by step and see what is actually happening. Another thing that helps is adding return statement, especially if you come from language like Java because it is more understandable what is happening.
Your function with return would looks like this:
def sum(xs: List[Int]): Int = {
if(xs.isEmpty)
return 0
else
return xs.head + sum(xs.tail)
}
In your case you have function that sums all integer in a list.
So lets imagine that you have called function using list with following values (1,2,3)
How will function behave?
First function call will look like this:
if(xs.isEmpty) // false - it has 3 elements (1,2,3)
return 0 // skipped
else
return 1 + sum((2,3)) // xs.head is changed with 1 and xs.tail is list with (2,3)
Second call is now with list (2,3):
if(xs.isEmpty) // false - it has 2 elements (2,3)
return 0 // skipped
else
return 2 + sum((3)) // xs.head is changed with 2 and xs.tail is list with (3)
Trird call is now with list (3):
if(xs.isEmpty) // false - it has 1 elements (3)
return 0 // skipped
else
return 3 + sum(()) // xs.head is changed with 3 and xs.tail is empty list now
Fourth call is with empty list:
if(xs.isEmpty) // true
return 0 // Recursion termination case triggered
So now we have our sum call stack looking something like this:
sum((1,2,3))
where sum = 1 + sum((2,3))
where sum = 2 + sum((3))
where sum = 3 + sum(())
where sum = 0
And we simply start returning values:
sum((1,2,3))
where sum = 1 + 5
where sum = 2 + 3
where sum = 3 + 0
so we end up with sum((1,2,3)) = 6
That is why we don't need to store "intermediate result", because calculating sum starts from the end and rolls backwards.
It might be helpful for you to think in terms of an actual example. Let's say we had:
List(1,3,5)
Passing this to the sum method, the first test would fail (the list is not empty). Then it would add the head item (i.e. 1) to the sum of the tail, i.e. sum(List(3,5)). So, the operation cannot complete, as it were, until the second expression is calculated, and sum is called a second time. The initial test fails (List(3,5) is not empty), and the method returns a value of 3 + sum(List(5)). Again it cannot complete until calculating the second expression, so sum is called again. Once again, the initial test fails as List(5) is not empty and this call returns a value of 5 + sum(List()). For the last time, sum is called, and this time the initial test succeeds and returns 0, so:
sum(List()) = 0
sum(List(5)) = 5
sum(List(3,5)) = 8
sum(List(1,3,5)) = 9
Figuring this sort of thing out is useful (and essential) to understanding recursion.
Both intermediate results (xs.head and sum(xs.tail)) are stored in so called frames which are memory regions in executing thread's Java stack. A separate frame is created for each nesting call of the sum function so those intermediate results are separate for each sum call.
From Java documentation:
A frame is used to store data and partial results, as well as to perform dynamic linking, return values for methods, and dispatch exceptions.
A new frame is created each time a method is invoked. A frame is destroyed when its method invocation completes, whether that completion is normal or abrupt (it throws an uncaught exception). Frames are allocated from the Java Virtual Machine stack (§2.5.2) of the thread creating the frame. Each frame has its own array of local variables (§2.6.1), its own operand stack (§2.6.2), and a reference to the run-time constant pool (§2.5.5) of the class of the current method.
Here is how your code compiles into JVM byte-code:
public int sum(scala.collection.immutable.List<java.lang.Object>);
Code:
0: aload_1
1: invokevirtual #63 // Method scala/collection/immutable/List.isEmpty:()Z
4: ifeq 11
7: iconst_0
8: goto 30
11: aload_1
12: invokevirtual #67 // Method scala/collection/immutable/List.head:()Ljava/lang/Object;
15: invokestatic #73 // Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
18: aload_0
19: aload_1
20: invokevirtual #76 // Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
23: checkcast #59 // class scala/collection/immutable/List
26: invokevirtual #78 // Method sum:(Lscala/collection/immutable/List;)I
29: iadd
30: ireturn
Note the iadd instruction near the end. From description of iadd instruction:
Both value1 and value2 must be of type int. The values are popped from the operand stack. The int result is value1 + value2. The result is pushed onto the operand stack.
