Scala Tail Recursive to Not Tail Recursive

Question

This may be a weird question but...

Question: How do I turn a tail-recursive function in Scala into a non-tail-recursive solution?

Note: I am aware tail recursive solutions are great in Scala, but I was asked to change it into a non-tail recursive solution. I have no idea how to do that

I have my code for a tail-recursive solution here (at least I hope it's tail recursive lol)

def cubesTailRecur(a: List[Int], acc: List[Int] = List.empty): List[Int] = {
      a match {
        case Nil => acc
        case h :: t if (h%2 == 0) => cubesTailRecur(t, acc)
        case h :: t  => cubesTailRecur(t, acc :+ Math.pow(h, 3).toInt)
      }
    }

What my function does is iterate through a given List of integers and returns a new array with the cubes of all the odd numbers.

Example:

    println(cubesTailRecur(List(1, 2, 3, 4, 5, 6, 7)))

    // OUTPUT
    // List(1, 27, 125, 343)

lztachyon · Accepted Answer · 2017-10-06T05:35:39.047

4

Tail recursion is a form of recursion in which recursive call is the last instruction. To not make something tail recursive would mean that you need to do some other computation with the result of the recursive call.

In your case, you can remove the acc/accumulator parameter and perform accumulation through recursive stack. Something along the following lines,

def cubesRec(a: List[Int]): List[Int] = a match {
  case Nil => List[Int]()
  case h::t if (h%2 == 0) => cubesRec(t)
  case h::t => Math.pow(h,3).toInt :: cubesRec(t)
}

edited Oct 06 '17 at 05:35

answered Oct 06 '17 at 05:19

lztachyon

116
6

This works but there's one issue. It prints the list in reverse order. For example: List(1, 27, 125, 343) vs. List(343, 125, 27, 1) – Phil Oct 06 '17 at 05:23
How would I reverse it? Edit: How do I reverse it within the function. I know how to reverse while printing – Phil Oct 06 '17 at 05:23
you could prepend the `Math.pow(h,3).toInt` using `Math.pow(h,3).toInt :: cubesRec(t)` – lztachyon Oct 06 '17 at 05:29
Quick question: How come using `+:` and `::` both prepend. I just tested out both – Phil Oct 06 '17 at 05:32
1

`::`, also known as cons is defined only for list, where as `+:` is defined for `Seq` which is bit generic. Take a look at [this question](https://stackoverflow.com/questions/11814675/whats-the-difference-between-and-for-prepending-to-a-list) to understand better – lztachyon Oct 06 '17 at 05:36

Scala Tail Recursive to Not Tail Recursive

1 Answers1

Linked

Related