Q:

scala recursive functions throws Stackoverflow exception

def bubblesort(xs: List[Int]): List[Int] = xs match {
    case List()  => List()
    case List(x) => List(x)
    case x :: y :: rest =>
      {
        def bubbled(x1: Int, y1: Int) = {
          val (first, second) = if (x1 > y1) (y1, x1) else (x1, y1)
          first :: bubblesort(second :: rest)
        }
        bubblesort(bubbled(x, y).init) ++ List(bubbled(x, y)).last
      }
  }

1. The above code Stackoverflow exception, actually I translated the same code from the below haskell code in scala.
bubblesort2 :: (Ord a, Show a) => [a] -> [a]
bubblesort2 [] = []
bubblesort2 [x] = [x]
bubblesort2 (x:y:rest) =
    bubblesort2 (init bubbled) ++ [last bubbled]
    where
        (first,second) = if x > y then (y,x) else (x,y)
        bubbled = first : bubblesort2(second:rest)

What is wrong with the scala code ?

A:

You made error in scala code:
bubblesort2 (init bubbled) ++ [last bubbled]

should be translated as 
bubblesort(bubbled(x, y).init) :+ bubbled(x, y).last

In your code bubblesort(bubbled(x, y).init) ++ List(bubbled(x, y)).last
 leads you to infinite recursion.

