# Tail Recursion

FILE : HighOrderFunctionsDemo

In the file you will find two sum functions. First implementation is the most obvious ,

1. Add first element to sum
2. repeat for the rest of a list
3. stop when list is empty
`````` def unsafeSum(n:Int):Int =
if(n<=0) 0
else n + unsafeSum(n-1)
``````

The problem with this one is that each call adds another memory cell to stack, so at some point we will observe stack overflow.

``````  section("unsafeSum(5)",unsafeSum(5))
//      section("unsafeSum(500000000)",unsafeSum(500000000))  //---> Stack overflow
``````

Yet in scala there is a solution for this situation.

``````def safeSum(n:Int):Int = {
@tailrec
def internalLoop(actual:Int,sum:Int):Int=
if(actual<=0) sum
else internalLoop(actual-1,sum+actual)

internalLoop(n,0)
}
``````

We are using two concepts here :

• Internal function invisible from outside which is used to triger recursion cycle
• notice that internal loop as the last instruction has always only call to itself. So it is easy to actually use the same stack frame to store result. To achieve this you need to pass partial result to each call.

In practice tailrec calls are converted to simple while loop :

``````public int internalLoop(int, int);
Code:
1: iconst_0
2: if_icmpgt     9
6: goto          20
10: iconst_1
11: isub
15: istore_2
16: istore_1
17: goto          0
20: ireturn
``````

So no problems here :

``````section("safeSum(5)",safeSum(5))
section("safeSum(500000000)",safeSum(500000000))
``````

Also check how @tailrec is working. If you will add this to unsafeSum you will see compilation error. So great help from compiler!!

``````Error:(21, 12) could not optimize @tailrec annotated method unsafeSum: it contains a recursive call not in tail position
else n + unsafeSum(n-1)
``````

EXERCISES

FILE : TailRecursionExercises

EXERCISE 1

Uncomment tailrec and implement safe list sum function

``````//@tailrec - UNCOMMENT FOR EXERCISe
def sumList(list:CustomList,sum:Int=0):Int = ???
``````

EXERCISE 2

You have custom List implementation

``````sealed trait CustomList
case class ListElem(a:Int,rest:CustomList) extends CustomList
case object ListEnd extends CustomList
``````

Which allow you to generate linked list :

``````ListElem(6,ListElem(6,ListElem(6,ListEnd)))
``````

Implement generator of such lists

EXERCISE 3

Implement tail safe reduce left which will join all elements into one according to passed recipe

``````val l1=ListElem(2,ListElem(3,ListElem(4,ListEnd)))

reduceLeft(l1)(0)(_+_) mustBe 9
reduceLeft(l1)(1)(_*_) mustBe 24
``````