Scala: Tail Recursion and ListBuffer

Question

I am learning Scala and in the course of doing so I follow the 15 exercises of Brien (http://www.knowing.net/index.php/2006/06/16/15-exercises-to-know-a-programming-language-part-1/) In the second exercise I should implement a Haar transformation. I implemented most of it but struggled several hours with the return value of the tail recursion. As the compiler doesn't compile `++` - or more exactly the line `haar(averages) ++ haar(averagesD)`. - What I am doing wrong in the recursive function? - Can you give me other feedback on my code? Code: ``` import scala.collection.mutable.ListBuffer import scala.annotation.tailrec object haarWavelet2 { def avg(tpl:Tuple2[Double, Double]):Double = (tpl._1 + tpl._2) / 2. def avgD(tpl:Tuple2[Double, Double]):Double = (tpl._1 - tpl._2) / 2 def total_avg(nums:ListBuffer[Double]):Double = nums.sum / nums.length @tailrec def haar(nums:ListBuffer[Double]):ListBuffer[Double] = { if (nums.length == 1) {return nums} val buffer = new ListBuffer[Tuple2[Doubl…

Accepted Answer

Tail recursion has the following form:

```
def func(x..., value){
  if(condition) return value
  else func(y..., value')
}
```

If you look at this form, what you see is that in order to evaluate `func` all I need is `func` itself but with a different set of arguments. Therefore, there is only one item to be placed on the stack and it can easily be transformed into an iterative algorithm.

What you've implemented looks like this:

```
def func(x...){
  if(condition) return value
  else func(y...) + func(z...)
```

Notice that in order to evaluate `func` that you must first evaluate `func`, an operator `+` and then 'func' again. So that's 3 items that need to be placed on the stack with a very real order of evaluation which is not amenable to tail call optimization.

Scala: Tail Recursion and ListBuffer

Solution

Problem