Experimenting with recursion and ZIO

If you’re already comfortable with recursion, you can skip the first part introducing tail-recursion and go directly to the ZIO section.

Introduction: recursion and functional programming

Recursion is one of the main techniques used in functional programming to replace an iterative loop. One of the most common examples is the Fibonacci computation or factorial computation. For this experiment, we will focus on an even simpler function: summing the numbers from 1 to n. Of course, we won’t use the mathematical formula to compute it in constant time.

Iterative implementation

def sumIterative(n: Int): Int = {
  var res = 0
  for (i <- 1 to n) { res += i }
  return res
}

The iterative version requires a mutable variable to store the result. We add each number from 1 to n into it thanks to a for-loop.

Naive recursive implementation

def sumRecursive(n: Int): Int = {
  if (n == 0) 0
  else sumRecursive(n - 1) + n
}

This recursive version is the simplest one possible: adding n to the sum from 1 to n-1. However, for a big integer, it can cause a stack overflow because of the third line: it needs the result sumRecursive(n-1) to be able to sum it with n. Thus, it requires to keep on the call stack all the operations until the leaf operation, which is n == 0. Below is an illustration of the stack for n = 5:

> sumRecursive(5)
>> sumRecursive(4)
>>> sumRecursive(3)
>>>> sumRecursive(2)
>>>>> sumRecursive(1)
>>>>>> sumRecursive(0)
<<<<<< 0
<<<<< 0 + 1 = 1
<<<< 1 + 2 = 3
<<< 3 + 3 = 6
<< 6 + 4 = 10
< 10 + 5 = 15

From it, we can easily imagine the stack can become huge for big integers. Indeed we need to go all the way to 0 and then sum it up. Consequently leading to a stack overflow error.

Tail-recursive solution: avoiding the stack overflow

The issue with the previous solution is that it needs to compute something with the result of the recursive call, which makes it non-tail recursive. A tail-recursive call, instead, won’t compute anything from the recursive result. Considering a stack of operations, it is the last call, meaning there is no operation needed after it. And thanks to that the compiler is able to optimize those calls by “emptying” the call stack. In Scala, we need to mention a function is tail-recursive with the @tailrec annotation, so the compiler is able to optimize the call stack.

So, instead of storing in the call stack the intermediate results (represented directly by their calls), we need to use an accumulator which accumulates the result at every step. That’s equivalent to the iterative res variable but as a function parameter, so we can pass it from call to call. Instead of the leaf case, we do return the accumulator directly.

@tailrec
def sumTailRecursive(n: Int, res: Int = 0): Int = {
  if (n == 0) res
  else sumTailRecursive(n-1, res + n)
}

Now, the call stack becomes:

> sumTailRecursive(5, 0)
> sumTailRecursive(4, 0 + 5)
> sumTailRecursive(3, 5 + 4)
> sumTailRecursive(2, 0 + 5 + 4 + 3)
> sumTailRecursive(1, 0 + 5 + 4 + 3 + 2)
> sumTailRecursive(0, 0 + 5 + 4 + 3 + 2 + 1)
> 0 + 5 + 4 + 3 + 2 + 1 = 15

We can observe the addition is done directly inside the accumulator, instead of the call stack.

ZIO and tail-recursion

ZIO is a Scala library to handle asynchronous programming. It provides a developer-level API to manage effect calls in a fully functional programming way, it relies on the ZIO[R, E, A] which is an IO monad. Check out the official website, or our Knoldus blogs and templates.

Real use case: turning pages

One recurring use case when dealing with API is to process data in batch, thus by going through all the pages available. Let’s consider we have the code to reach a particular API page, which returns either the list of entities or a custom API error. There, we’ll consider only the 413 error code corresponding to a too big payload.

  sealed trait APIError
  case object TooBigPage extends APIError

  def getPage(page: Int, limit: Int): IO[APIError, Iterable[Entity]] = ???

Depending on whether the result is a success or not, we want to recur differently: if the page was too big, try again with a smaller page size otherwise, get the next page.

def readAllPages(page: Int = 0, limit: Int = 10): UIO[Unit] =
  getPage(page, limit).either
    .flatMap {
      case Right(entities) =>
        //Process entities
        readAllPages(page + 1, limit)
      case Left(TooBigPage) => readAllPages(page * 2, limit / 2)
    }

The magic of ZIO: it is stack safe!

This function has a tail-recursive feeling: the recursive call is in the tail position. However, the recursive call is nested inside a ZIO flatMap. So we can’t use the @tailrec annotation as usual (it won’t compile). Still, it works perfectly fine and doesn’t overflow the stack. How? In short, ZIO is handling that for you. Under the hood, ZIO is managing plenty of concurrent concerns including memory usage. That’s the beauty of this library/ecosystem: as a developer, you can focus on building user value (or deep dive into optimizing it by contributing to their libraries).