java.lang.OutOfMemoryError с хвостовой рекурсией - PullRequest
Новая
       4

java.lang.OutOfMemoryError с хвостовой рекурсией

1 голос
/ 07 октября 2019

Почему я получаю java.lang.OutOfMemoryError: пространство кучи Java, когда я вызываю первую функцию с большим числом, например 2000, и не получаю никакой ошибки от второй реализации?

Не будет ли зарезервировано одинаковое количество памяти? 

object TailRecursion extends App{

  @tailrec
  def repeatString (str: String, n:Integer ): String = {
    if (n == 0) ""
    else if (n == 1) str
    else repeatString(str+str, n-1)
  }

  @tailrec
  def repeatString(str:String, n:Integer, accumulator:String):String ={
    if(n==0) accumulator
    else repeatString(str, n-1, str+accumulator)
  }

  println(repeatString("teste", 0))
  println(repeatString("teste", 1))
  println(repeatString("teste", 2))
  println(repeatString("teste", 2000))
}

1 Ответ

0 голосов
/ 07 октября 2019

Нет. Оба не зарезервируют одинаковый объем памяти.

Давайте попробуем сделать один с ошибкой OutOfMemory с выражением for в Scala. Он будет примерно переведен в следующий код: 

def repeatStringLoop(string: String, n: Integer): String = {
  var resultString = string
  if (n == 0) ""
  else if (n == 1) string
  else {
    for (i <- 0 until n) {
      resultString = resultString.concat(resultString)
    }    
    resultString
  }
}

Если вы запустите код, он выдаст ту же ошибку. Это потому, что вы пытаетесь объединить каждую модифицированную строку дважды - что приводит к увеличению объема памяти - что не совпадает со строкой сцепления "teste" со строкой результата.

Однако для этого лучше использовать StringBuilderвид конкатенации строк.

...