Ответ 1

Это не хвостовая рекурсия

Предположим, что вы делали список вместо потока: (позвольте мне использовать более простую функцию, чтобы сделать мою точку)

def foo(n: Int): List[Int] =
  if (n == 0)
    0 :: Nil
  else
    n :: foo(n - 1)

В общем случае в этой рекурсии после foo(n - 1) возвращается функция должна что-то сделать с возвращаемым списком - она ​​должна конкатенировать другой элемент в начале списка. Таким образом, функция не может быть хвостичной рекурсивной, потому что что-то должно быть сделано в списке после рекурсии.

Без хвостовой рекурсии для некоторого большого значения n у вас закончится пространство стека.

Обычное решение списка

Обычным решением было бы передать ListBuffer в качестве второго параметра и заполнить его.

def foo(n: Int) = {
  def fooInternal(n: Int, list: ListBuffer[Int]) = {
    if (n == 0) 
      list.toList
    else {
      list += n
      fooInternal(n - 1, list)
    }
  }
  fooInternal(n, new ListBuffer[Int]())
}

То, что вы делаете, называется " хвостовая рекурсия по модулю минус", и это оптимизация, выполняемая автоматически с помощью LISP Пролог-компиляторы, когда они видят хвостовую рекурсию по модулю против шаблона, так как это так распространено. Scala компилятор не оптимизирует это автоматически.

Потокам не нужна рекурсия хвоста

Потоки не нуждаются в хвостовой рекурсии, чтобы избежать нехватки стека - это потому, что они используют умный трюк, чтобы не выполнять рекурсивный вызов foo в точке, где он отображается в коде. Вызов функции завершается в thunk и только вызывается в точке, в которой вы фактически пытаетесь получить значение из потока. Только один вызов foo активен одновременно - он никогда не рекурсивный.

Я написал предыдущий ответ, объясняющий как работает оператор #:: здесь, в Stackoverflow. Здесь, что происходит, когда вы вызываете следующую рекурсивную функцию потока. (Он рекурсивный в математическом смысле, но он не вызывает вызов функции из вызова функции так, как вы обычно ожидаете.)

def foo(n: Int): Stream[Int] =
  if (n == 0)
    0 #:: Nil
  else
    n #:: foo(n - 1)

Вы вызываете foo(10), он возвращает поток с одним уже вычисленным элементом, а хвост - это thunk, который вызовет foo(9) в следующий раз, когда вам понадобится элемент из потока. foo(9) теперь не вызывается - скорее, вызов привязан к lazy val внутри потока, а foo(10) возвращается немедленно. Когда вам наконец понадобится второе значение в потоке, вызывается foo(9), и он вычисляет один элемент и устанавливает хвост потока hte как thunk, который вызывается foo(8). foo(9) немедленно возвращается без вызова foo(8). И так далее...

Это позволяет создавать бесконечные потоки без исчерпания памяти, например:

def countUp(start: Int): Stream[Int] = start #::countUp(start + 1)

(Будьте осторожны, какие операции вы вызываете в этом потоке. Если вы попытаетесь сделать forEach или map, вы заполните всю свою кучу, но использование take - это хороший способ работать с произвольный префикс потока.)

Более простое решение

Вместо того, чтобы иметь дело с рекурсией и потоками, почему бы просто не использовать цикл Scala for?

def pairs(maximum:Int) =
  for (i <- 0 to maximum;
       j <- 0 to maximum)
    yield (i, j)

Это материализует всю коллекцию в памяти и возвращает IndexedSeq[(Int, Int)].

Если вам нужен Stream, вы можете преобразовать первый диапазон в Stream.

def pairs(maximum:Int) =
  for (i <- 0 to maximum toStream;
       j <- 0 to maximum)
    yield (i, j)

Это вернет a Stream[(Int, Int)]. Когда вы получаете доступ к определенной точке в последовательности, она будет материализована в память, и она будет придерживаться до тех пор, пока вы все еще будете ссылаться на любую точку в потоке перед этим элементом.

Вы можете получить еще лучшее использование памяти, преобразовывая оба диапазона в представления.

def pairs(maximum:Int) =
  for (i <- 0 to maximum view;
       j <- 0 to maximum view)
    yield (i, j)

Это возвращает SeqView[(Int, Int),Seq[_]], который вычисляет каждый элемент каждый раз, когда вам это нужно, и не сохраняет предварительно вычисленные результаты.

Вы также можете получить итератор (который вы можете перемещать только один раз) таким же образом

def pairs(maximum:Int) =
  for (i <- 0 to maximum iterator;
       j <- 0 to maximum iterator)
    yield (i, j)

Возвращает Iterator[(Int, Int)].

Ответ 2

Может быть, Итератор лучше подходит вам?

class PairIterator (max: Int) extends Iterator [(Int, Int)] {
  var count = -1
  def hasNext = count <= max * max 
  def next () = { count += 1; (count / max, count % max) }
}

val pi = new PairIterator (5)
pi.take (7).toList