Skip to content

Instantly share code, notes, and snippets.

@wmhtet
Created November 23, 2011 04:42
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save wmhtet/1387911 to your computer and use it in GitHub Desktop.
This is the recursion example (p.97) used in "Programming Interviews Exposed" by John Mongan, Noah Suojanen, Eric Giguère The book's imperative style C# code (function combine) has been reimplemented in Scala. Function recursionEx is in pure FP way.
/*
http://blog.aunndroid.com/2011/11/learning-scala-recursion-and-tco-1.html
This is the recursion example (p.97) used in "Programming Interviews Exposed"
by John Mongan, Noah Suojanen, Eric Giguère
The book's imperative style C# code (function combine) has been reimplemented in Scala.
Function recursionEx is in pure FP way.
Function tailReccursionEx is implemented to get TCO'ed (TCO=Tail Call Optimization)
Here is the problem statement:
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".
*/
import scala.collection.immutable._
object RecursionEx {
def main(args : Array[String]) = {
//val input="123456"
val input = "wxyz"
val result = recursionEx(input).sorted
println(result.length + " : " + result.mkString(" "))
combine(input)
val tail = tailReccursionEx(input)
println("tail: " + tail.length + " : " + tail.mkString(" "))
}
def combine(str : String) : Unit = {
def doCombine(instr : List[Char], outStr : StringBuilder, length : Int, level : Int, start : Int) : Unit = {
for (i <- start until length) {
outStr.append(instr(i))
println(outStr)
if (i < length - 1) { doCombine(instr, outStr, length, level + 1, i + 1) }
outStr.setLength(outStr.length() - 1)
}
}
doCombine(str.foldLeft(List[Char]()) {
(l, ch) => l :+ ch
}, new StringBuilder(""), str.length, 0, 0)
}
def recursionEx(str : String) : List[String] = {
if (str.length == 1) return List(str)
List(str.head.toString) ++ recursionEx(str.tail)
.foldLeft(List[String]()) {
(il, sub) => str.head + sub :: sub :: il
}
}
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]())
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment