CODEWITHSUNDEEP
scalatail
Vikas Pandya
Vikas Pandya

Reputation: 1988

Tail recursion cons operator Scala

If the last statement in a function is func(x,tailList):

    def func(x:Int):List[Int]...
    case head :: tailList => head :: func(x,tailList)

converting this function to tail recursion requires accumulator to be added as a third parameter (and to keep it clean adding a local function inside func() ). 

    insertTail(x,tailList,head::acc)

doesn't seem to work correctly. shouldn't "acc" hold the computation in progress?

Am I missing something here to make it tail recursive work with accumulator?

Adding a more complete example

def funcTailTest(x:Int,xs:List[Int]):List[Int] =  {
@tailrec
def inner(x:Int,xs:List[Int],acc:List[Int]) : List[Int] = xs match {

  case head::tailList => {
    inner(x,tailList,head::acc)
  }
}
inner(x,xs,Nil)

}

basically head should be added to the output of inner() function so w/o an attempt to make it tail recursive last statement in a case will look

head::inner(x,tailList)

Upvotes: 0

Views: 1847

Answers (2)

Selvaram G
Selvaram G

Reputation: 748

Following is a scala function to implement Tail recursion using cons operator

def reverseUtility(ele: List[Int], res: List[Int]):List[Int] ={
  ele match {
  case Nil => Nil
  case x :: Nil => x :: res
  case x :: y => reverseUtility(y, (x::res))
}}

Pass a list of Int and an empty list called res(result) as parameters for the function. Time complexity for the function is O(N)

Upvotes: 1

Malte Schwerhoff
Malte Schwerhoff

Reputation: 12852

Assuming that reverse is also tail recursively implemented (which it definitely can be), the following is a tail recursive append:

def append[T](y: T, xs: List[T]): List[T] = {
  @tailrec
  def appendAcc[T](y: T, xs: List[T], acc: List[T]): List[T] = xs match {
    case Nil => y :: acc
    case x :: xs => appendAcc(y, xs, x :: acc)
  }

  appendAcc(y, xs, Nil).reverse
}

Upvotes: 1

Related Questions