Scala StackOverflowError mentre Java in grado di gestirlo

Question

Sono appoggiato a programmare in Scala e sono imbattuto in questo problema in cui codice Scala getta StackOverflowErorr mentre simile implementazione in Java può andare un po 'di più prima di lanciare lo stesso errore

def recursiveSum(args: Int*): Int = { 
    if (args.length == 0) 0 
    else 
     args.head + recursiveSum(args.tail: _*) 

    }            

    recursiveSum(5000 to 15000: _*) 

Il errore ottengo è

java.lang.StackOverflowError 
//|  at scala.collection.Parallelizable$class.$init$(Parallelizable.scala:20) 
//|  at scala.collection.AbstractTraversable.<init>(Traversable.scala:105) 
//|  at scala.collection.AbstractIterable.<init>(Iterable.scala:54) 
//|  at scala.collection.AbstractSeq.<init>(Seq.scala:40) 
//|  at scala.collection.immutable.Range.<init>(Range.scala:44) 
//|  at scala.collection.immutable.Range$Inclusive.<init>(Range.scala:330) 
//|  at scala.collection.immutable.Range$Inclusive.copy(Range.scala:333) 
//|  at scala.collection.immutable.Range.drop(Range.scala:170) 
//|  at scala.collection.immutable.Range.tail(Range.scala:196) 
//|  at scala.collection.immutable.Range.tail(Range.scala:44) 
//|  at Loops$$anonfun$main$1.recursiveSum$1(Loops.scala:11) 
//|  at Loops$$anonfun$main$1.recursiveSum$1(Loops.scala:11) 
//|  at Loops$$anonfun$main$1.recursiveSum$1(Loops.scala:11) 
//|  at Loops$$anonfun$main$1.recursiveSum$1(Loops.scala:11) 
//|  at Loops$$anonfun$m 
//| Output exceeds cutoff limit. 

il codice Java è

static int recursiveSum(int... arg) { 
     if (arg.length == 0) 
      return 0; 
     else 
      return arg[0] + recursiveSum(Arrays.copyOfRange(arg, 1, arg.length)); 
    } 

    public static void main(String[] args) { 
     System.out.println(recursiveSum(range(5000, 15000))); 
    } 

    private static int[] range(int i, int j) { 
     int list[] = new int[j - i + 1]; 
     int idx = 0; 
     for (int s = i; s <= j; s++) 
      list[idx++] = s; 
     return list; 
    } 

Perché l'aiuto dell'ottimizzazione della ricorsione di coda di Scala non è d'aiuto? Com'è possibile gestire Java (Java non può gestire più di 15000 dire anche 16000)?

Vengono eseguiti sullo stesso ide di eclissi con le dimensioni di stack predefinite di java 7 sulla macchina desktop.

Answer 1

Questo non è ricorsiva coda. Affinché la funzione sia ricorsiva in coda, l'ultima istruzione (la coda) nella funzione deve essere la chiamata ricorsiva. Nel tuo caso, potrebbe sembrare come è, ma se annoti la tua funzione con l'annotazione @tailrec, vedrai che non lo è. In effetti, la tua ultima affermazione è un'aggiunta, non la chiamata ricorsiva.

Se si riscrive la funzione di usare un accumulatore, sarete in grado di fare una versione ricorsiva di coda ...

def recursiveSum(args: Int*): Int = { 
    @tailrec 
    def sumAccumulator(sum: Int, args: Int*): Int = { 
     if(args.length == 0) sum 
     else sumAccumulator(sum + args.head, args.tail: _*) 
    } 
    sumAccumulator(0, args: _*) 
} 

recursiveSum(5000 to 15000: _*) 

Answer 2

La funzione non è formattata correttamente per la ricorsione della coda. È possibile verificare questo (tentando di) aggiungere l'annotazione @tailrec.

scala> import annotation.tailrec 
import annotation.tailrec 

scala> @tailrec def recursiveSum(args: Int*): Int = { 
    |  if (args.length == 0) 0 
    |  else 
    |  args.head + recursiveSum(args.tail: _*) 
    | 
    | } 
<console>:11: error: could not optimize @tailrec annotated method recursiveSum: it contains a recursive call not in tail position 
      args.head + recursiveSum(args.tail: _*) 

       ^

Ecco una soluzione di lavoro:

import annotation.tailrec 
def recursiveSum(args: Int*): Int = { 
    @tailrec def recursiveSumInternal(sum : Int, args: Int*): Int = { 
     if (args.length == 0) 
      sum 
     else 
      recursiveSumInternal(sum+args.head, args.tail: _*) 
    } 
    recursiveSumInternal(0, args: _*) 
} 

recursiveSum(5000 to 15000 : _*)