Tail Recursion

FILE : TailRecursionDemo

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:
       0: iload_1
       1: iconst_0
       2: if_icmpgt     9
       5: iload_2
       6: goto          20
       9: iload_1
      10: iconst_1
      11: isub
      12: iload_2
      13: iload_1
      14: iadd
      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