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.

RecursionEx.scala

/*
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]())
	}
}