Переполнение стека при запуске хвостового рекурсивного метода

Question

Я проверяю эффективность оптимизации хвостовой рекурсии в Scala. Поэтому я тестирую его как в eclipse, так и в sbt. Тем не менее, я получаю только результат, что версия рекурсии хвоста работает намного хуже, чем обычная. Интересно, зачем.

И вот мой код.

package MyList 

sealed trait List[+A] 
case object Nil extends List[Nothing] 
case class Cons[+A](head: A, tail: List[A]) extends List[A] 

object List { // companion object 

    def sum(ints: List[Int]): Int = ints match { 
    case Nil => 0 
    case Cons(x, xs) => x+sum(xs) 
    } 

    def sum_tail_recursion(ints: List[Int]): Int = { 
    @scala.annotation.tailrec 
    def helper(ls: List[Int], res: Int): Int = ls match { 
     case Nil => res 
     case Cons(x, xs) => helper(xs, res+x) 
    } 
    helper(ints, 0) 
    } 

    def generate_tail_recursion(n: Int): List[Int] = { 
    @scala.annotation.tailrec 
    def helper(x: Int, ls: List[Int]): List[Int] = x match { 
     case 0 => ls 
     case x => helper(x-1, Cons(x, ls)) 
    } 
    helper(n, Nil) 
    } 

    def generate(n: Int): List[Int] = n match { 
    case 0 => Nil 
    case x => Cons(x, generate(x-1)) 
    } 

    def time[A](block: => A): A = { 
    val t0 = System.nanoTime() 
    val result = block 
    val t1 = System.nanoTime() 
    println("Elapsed time: " + (t1-t0) + "ns") 
    result 
    } 
} 

Кроме того, я считаю, что generate(10000) вызовет переполнение стека, но generate_tail_recursion(10000) не будет. (Но последнее вызовет некоторую ошибку toString.Как я могу ее решить?) Итак, как я могу улучшить производительность, используя хвостовую рекурсию в Scala? Благодаря!

Обновление:

Вот ошибки.

Когда я запускаю 'генерировать (10000)':

java.lang.StackOverflowError at scala.runtime.BoxesRunTime.boxToInteger(BoxesRunTime.java:70) at MyList.List$.generate(List.scala:56) at MyList.List$.generate(List.scala:56) at MyList.List$.generate(List.scala:56) at MyList.List$.generate(List.scala:56)

Когда я бегу generate_tail_recursion(10000):

java.lang.StackOverflowError at scala.collection.AbstractIterator.addString(Iterator.scala:1157) at scala.collection.TraversableOnce$class.mkString(TraversableOnce.scala:286) at scala.collection.AbstractIterator.mkString(Iterator.scala:1157) at scala.runtime.ScalaRunTime$._toString(ScalaRunTime.scala:170) at MyList.Cons.toString(List.scala:5) at java.lang.String.valueOf(Unknown Source) at scala.collection.mutable.StringBuilder.append(StringBuilder.scala:197) at scala.collection.TraversableOnce$$anonfun$addString$1.apply(TraversableOnce.scala:327) at scala.collection.Iterator$class.foreach(Iterator.scala:727) at scala.collection.AbstractIterator.foreach(Iterator.scala:1157) at scala.collection.TraversableOnce$class.addString(TraversableOnce.scala:320) at scala.collection.AbstractIterator.addString(Iterator.scala:1157) at scala.collection.TraversableOnce$class.mkString(TraversableOnce.scala:286) at scala.collection.AbstractIterator.mkString(Iterator.scala:1157) at scala.runtime.ScalaRunTime$._toString(ScalaRunTime.scala:170)

Answer 1

Вероятно, самое неожиданное, что здесь является то, что вы, кажется, получают переполнение стека из хвостовой рекурсивной версии вашего метода, поэтому я объясню, почему это происходит.

Проще говоря, это потому, что вы используете generate_tail_recursion(10000) на консоли. Это вынуждает JVM попытаться построить String, описывающий весь список из 10 000 элементов, а затем распечатать его. Как вы можете себе представить, это будет массивная строка, потому что она будет выглядеть примерно как Cons(1,Cons(2,Cons(3,...,Cons(10000,Nil)...))). Вы можете подтвердить это сами, просто запустив generate_tail_recursion(10), чтобы увидеть крошечную версию этого. Итак, это то, что переполняет ваш стек.

Чтобы избежать печать немедленно весь список, вам нужно определить его в теле метода, например:

object Main { 
    private val Size = 10000 

    def main(args: Array[String]): Unit = { 
    val list = List time (List generate_tail_recursion Size) 
    //val list2 = List time (List generate Size) 
    } 
} 

Чтобы ясно понять, что именно Scala делает с @annotation.tailrec см https://stackoverflow.com/a/1682912/20371