O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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:

Tail call optimization

We need the stack ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required