CODEWITHSUNDEEP
scalatail-recursion
Srinivas
Srinivas

Reputation: 2100

Tail recursion in Scala

I have a question on scala tail recursion. I wrote a simple tail recursion code that takes a list and creates a new list of even numbers. But because of scala's inability to append elements to a list, my list is sorted in descending order. Below is the code

def listCreator(lists: List[Int]): List[Int] = {
    @tailrec
    def evenListCreator(lists: List[Int], accum: List[Int]): List[Int] = {
        lists match {
            case Nil => accum
            case x :: Nil if (isEven (x) == true) => x :: accum
            case x :: Nil if (isEven (x) == false) => accum
            case x :: tail if (isEven (x) == true) => evenListCreator(tail, x :: accum)
            case x :: tail if (isEven (x) == false) => evenListCreator(tail, accum)
        }
    }
    evenListCreator(lists, List()) 
}

I have the following questions

  1. How can I add a statement that reverses the list within this method?

  2. This line evenListCreator(lists, List()), which immediately follows the method call, is it mandatory for tail recursion?

Upvotes: 0

Views: 705

Answers (3)

jwvh
jwvh

Reputation: 51271

Q1. You can reverse the List before it is returned, as @Mahesh Chand Kandpal has pointed out, or you can build the list with the append method, accum :+ x, instead of the pre-pend ("cons") method, x :: accum.

But on a List the cons method is more efficient than the append method so it is usually better to build-and-reverse.

Q2. No. Tail recursion simply means that there are no other operations waiting after the call returns. In other words, return callMyself() is a tail-call but return callMyself() + 1 is not.

P.S. I know this is only a learning exercise but, really ...

def listCreator(ints: List[Int]): List[Int] = ints.filter(i => (i&1) < 1)

Upvotes: 2

Mahesh Chand
Mahesh Chand

Reputation: 3250

You can reverse before returning it.

scala> def listCreator(lists: List[Int]): List[Int] = {
     |     @tailrec
     |     def evenListCreator(lists: List[Int], accum: List[Int]): List[Int] = {
     |         lists match {
     |             case Nil => accum
     |             case x :: Nil if (isEven (x) == true) => x :: accum
     |             case x :: Nil if (isEven (x) == false) => accum
     |             case x :: tail if (isEven (x) == true) => evenListCreator(tail, x :: accum)
     |             case x :: tail if (isEven (x) == false) => evenListCreator(tail, accum)
     |         }
     |     }
     |     evenListCreator(lists, List.empty[Int]).reverse 
     | }
listCreator: (lists: List[Int])List[Int]

scala> listCreator((1 to 10).toList)
res2: List[Int] = List(2, 4, 6, 8, 10)

scala>

You don't need to immediately follow the method call but if you don't do you need to send two arguments one is list and second is empty list. So we take only list of integers so that one who is using, has not to bother like sending empty list also.

And You can do it directly also

scala> val list = (1 to 10).toList
list: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list.map(_ * 2)
res8: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

scala>

Upvotes: 2

Frederic A.
Frederic A.

Reputation: 3514

  1. evenListCreator(lists, List()).reverse or evenListCreator(lists.reverse, List()), but in your case the first form is better as the list to reverse will most likely be shorter after the call to evenListCreator
  2. this line: evenListCreator(lists, List()) doesn't follow the method call, it is the method call. Without it, nothing would happen as you would only define your tail recursive function (def evenListCreator) and return without calling it.

Some other notes

You have too many stop conditions, this is enough:

@tailrec
def evenListCreator(lists: List[Int], accum: List[Int]): List[Int] = {
  lists match {
    case Nil => accum
    case x :: tail if (isEven (x) == true) => evenListCreator(tail, x :: accum)
    case x :: tail if (isEven (x) == false) => evenListCreator(tail, accum)
  }
}

Code is too verbose, I think this is better:

@tailrec
def evenListCreator(lists: List[Int], accum: List[Int]): List[Int] = {
  lists match {
    case Nil => accum
    case x :: tail if isEven (x) => evenListCreator(tail, x :: accum)
    case x :: tail if !isEven (x) => evenListCreator(tail, accum)
  }
}

You can also call the recursive function that way:

evenListCreator(lists, Nil)

Upvotes: 2

Related Questions