Learning Functional Data Structures and Algorithms

Tail call optimization

We are using recursion to express looping. However, recursive code could result in a stack overflow. We need to understand an important optimization technique called tail call optimization (TCO). When TCO is applied, behind the scenes, recursion is expressed as a loop. This avoids stack frames, and subsequently, stack overflow.

For example, here is the preceding print method modified to print the range in reverse:

scala> def revprint(low: Int, high: Int): Unit = { 
     |   if (low <= high) { 
     |     revprint(low+1, high) 
     |     println(low) 
     |   } 
     | } 
scala> revprint(1,4) 
4 
3 
2 
1 

The following diagram shows the stack frames used:

We need the stack ...