// This import is needed for the @tailrec annotation. import annotation.tailrec // This worksheet explores issues in tail recursion // Direct (non-tail recursive) version of a method that creates multiple concatenations of // a string. The @tailrec annotation will produce a compile error here because the compiler // is not able to optimize this method to a loop. // // The issue is that the result of the recursive call is further processed before the method // returns. The pattern here is to immediately do the recursion to solve the subproblem and // then do additional computation to compute the result of the overall problem. // // @tailrec def repeat(n: Int, text: String): String = if (n == 0) "" else text + repeat(n - 1, text) // Imperative version of the same method. It is imperative because it modifies mutable vars. // The while loop evaluates to the Unit value (like Java's void) and so is only useful if // it has side effects (updating vars is a side effect). // // However this version uses O(1) stack space whereas the recursive version above will tend // to use O(n) stack space. For large n the imperative version thus has a distinct advantage. // def repeatImp(n: Int, text: String): String = { var workspace = "" var counter = n while (counter > 0) { workspace = text + workspace counter = counter - 1 } workspace } // Tail recursive version of the same method. It works by defining a local "helper" method // that accumulates the final result. The helper method takes the "current" state of the // computation as parameters and returns the answer. It works by calling itself on updated // computational state. The overall method then calls the helper using some suitable // initial state. // // The helper method is tail recursive because the result of the recursive call is immediately // the return value with no further processing needed. This allows the compiler to optimize // the method by replacing the recursive call with a jump to the start of the method (thus // turning the method into an imperative-style loop). As a result it also uses only O(1) // stack space. // // The @tailrec annotation is a request by the programmer to be told if the tail recursion // optimization is *not* actually used (either because the code isn't tail recursive after // all or because the compiler wasn't able to optimize it). The annotation does not affect // the code generated; the compiler will apply the optimization anyway if it can. It only // gives feedback to the programmer in the case when the optimization isn't actually used. // def repeatTR(n : Int, text: String): String = { // Tail recursive helper function to "accumulate" the result. @tailrec def doRepeat(numberLeft: Int, currentText: String): String = if (numberLeft == 0) currentText else doRepeat(numberLeft - 1, text + currentText) // Call the helper with suitable initial values. doRepeat(n, "") } // Let's do some testing... repeat(3, "Hello") repeatImp(3, "Hello") repeatTR(3, "Hello") // Another example from Homework #1 showing both the "direct" and tail recursive versions // of the method. As an exercise you might try writing the imperative version and comparing // it's structure to the two recursive methods. // def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1) def sumTR(n: Int): Int = { @tailrec def accumulate(currentValue: Int, currentSum: Int): Int = if (currentValue == 0) currentSum else accumulate(currentValue - 1, currentValue + currentSum) accumulate(n, 0) } sum(10) sumTR(10) // An example related to Homework #2. Note that A and B are generic type parameters. They // represent any type at all (the names A and B are conventional, but they could be any // names). This allows the method to work with lists with various element types. // Unzips a list of pairs into a pair of lists. // // val myList = List( (1, "x"), (2, "y"), (3, "z") ) // unzip(myList) = ( List(1, 2, 3), List("x", "y", "z") ) // def unzip[A, B](myList: List[(A, B)]): (List[A], List[B]) = myList match { case Nil => (List(), List()) case (head1, head2) :: tail => val (tail1, tail2) = unzip(tail) (head1 :: tail1, head2 :: tail2) } // For good measure here is the tail recursive version of the earlier method... def unzipTR[A, B](myList: List[(A, B)]): (List[A], List[B]) = { @tailrec def accumulate(currentLists: (List[A], List[B]), leftovers: List[(A, B)]): (List[A], List[B]) = leftovers match { case Nil => currentLists case (head1, head2) :: tail => accumulate( (head1 :: currentLists._1, head2 :: currentLists._2), tail) } // The accumulate helper method actually returns the list in reverse order so before // returning from the enclosing method, I will reverse them. // val (answer1, answer2) = accumulate( (List(), List()), myList ) (answer1.reverse, answer2.reverse) } val myList = List( (1, "x"), (2, "y"), (3, "z") ) unzip(myList) unzipTR(myList)