Second try

tims-recursion2.scala

scala>  def recurse(times: Int)(what : String)(how: String => String): String = {
     |     def rpt(times: Int, previous: => String): String = {
     |       println("Agg: " + previous)
     |       times match {
     |         case 0 => println("Done"); previous
     |         case _ => println("Recursing"); rpt(times - 1, how(previous))
     |       }
     |     }
     |     rpt(times, what)
     |   }
recurse: (times: Int)(what: String)(how: (String) => String)String

scala> 

scala> 

scala> def replace(rules: List[(String,String)])(what: String): String = 
     |     rules.foldLeft(what)((seed,tuple) => 
     |       seed.replaceAll(tuple._1,tuple._2))
replace: (rules: List[(String, String)])(what: String)String

scala> recurse(5)("A")(replace(List("A"->"ABCD")))
Agg: A
Recursing
Agg: ABCD
Recursing
Agg: ABCDBCD
Recursing
Agg: ABCDBCDBCD
Recursing
Agg: ABCDBCDBCDBCD
Recursing
Agg: ABCDBCDBCDBCDBCD
Done
res6: String = ABCDBCDBCDBCDBCD