Learning Scala : Recursion and TCO 2

Authored by Win Myo Htet

In the previous post, we talk about the TCO. Now, we will do some TCO'ed recursion exercise. I have picked an example  from "Programming Interviews Exposed" on P.97. Here is the problem definition : "Implement a function that prints all possible combinations of the characters  in a string. These combinations range in length from one to the length of the string. Two combinations that differ only in ordering of their characters are the same combination. In other words, "ab" and "ca" are different combinations from their input string "abc". But "ba" is the same as "ab""

We want to write a tail call recursive code with accumulator, which will give us the final result, at the end of iteration. We have to remember that we don't want any computation on the way back in these recursive calls. We will accumulate the result along the way so that we don't have to do backtrack computing. Before we go on analyzing the code, let me disclose something first. In the past, when I started coding, I tried to implement this problem by myself without reading at the authors' analysis. I failed. :) I was quite frustrated with my attempts and didn't try it again until I have started learning recursion in Scala. I try again this time. Yay! I made it. ;) With these experience, I have understood the problem and answer well. I am able to do educated grouping to form some patterns.

Yet, I still need paper and pencil! Nothing can beat paper and pencil in this age of computing when it comes to do pattern analyzing scratches for the problem. Holding pencil in the right hand like a sword, while paper in the left hand like a shield, I march on! When I am implementing the simple recursion for this problem, I look at the two logically grouped tables in the book (I won't be drawing these tables here. Buy the book!) It helps me with my thinking and visualizing of the data grouping and the flow of the data in the code too. Now, I am trying to go through the data flow where I don't have to backtrack for computing, the following data flow emerge.

input: w x y z 
=======
result: w wx wxy wxyz wxz wy wyz wz x xy xyz xz y yz z 

mydata flow
-----------
w
x
  wx 
y
  wy  xy
          wxy
z
  wz  xz  
          wxz
               yz
                   wyz  xyz  
                             wxyz  

Authored by Win Myo Htet


First, we will have 'w', which we will carry it in our accumulator to the next iteration. Then, we have 'x'. We will keep the 'w'. We want to add 'x' and also our first combination of character 'wx' too. I would like to go over this again. We start with 'w'. Carry it over. Get a new character 'x', keep the 'w', add the new 'x' and add 'w' and 'x' combination. Carry all these over in the accumulator to the next iteration. We still want to keep whatever we have before and add a new 'y' and the new characters combinations of 'y' and the previous list. Now, you know what happens to Z. If you don't, well, read this whole paragraph recursively until you get it. ;)

So basically, we have the accumulator and add a new character to the accumulator and also add a new list which has the combination of the new character with the string in the accumulator. Cool!

import scala.annotation.tailrec
 final def tailReccursionEx(str : String) : List[String] = {

  @tailrec
  def doTailRecursionEx(str : String, pos : Int, accu : List[String]) : List[String] = {
   if (pos == str.length) return accu
   else {
    val newAccu = accu ++ accu.foldLeft(List[String](str(`pos`).toString)) {
     (l, ch) => l :+ ch + str(`pos`)
    }
    doTailRecursionEx(str, pos + 1, newAccu)
   }
  }

  doTailRecursionEx(str, 0, List[String]())
 }

To make life simpler, I have started foldLeft process with the List with the new character. You can get the complete source code here .

When you look at the complete source code from the provided git repo link. You will see the comparison of imperative, recursion and TCO'ed recursion. They all look comparable. Here is another FP recursion implementation from the book (the one after the above example). When I implement the regular recursion, I am able to write it out. However, I have to make considerable effort to get it TCO'ed. The TCO'ed code is more verbose than regular recursion and at the same time also suffer from the performance impact.

Why do we want TCO again? To prevent side effect. To prevent stack over flow. To prevent our precious application from crashing. Is TCO worth the time and energy? Do you have better tip and trick ? Please let me know. I get to this haskell thread when I start looking into recursion via Ackermann.  I was thinking of implementing it TCO'ed. Having read the thread and seeing the TCO destroy the beauty of recursion and the extent needed to go to achieve the TCO, I don't want to try anymore. Yup, these are the ugly sides of FP and recursion. It is the different side of the same coin. We need to have discussion going how to tackle these issue to get FP traction for wider use. Here is one of the methods called trampoline to address some TCO issue in Scala. It is still not easy to use. It is advanced stuff. Well, it's an option.

StackOverflow discussion on this.

Authored by Win Myo Htet