Я создаю дерево пользовательских объектов в Scala, и мой метод вставки создает переполнение стека, потому что это не хвостовая рекурсия. Однако я не могу понять, как сделать его рекурсивным. Связанные примеры, которые я видел, используют переменные «накопителя», но это либо такие вещи, как целые числа, которые можно просто умножить и перезаписать, либо списки, которые у меня возникают проблемы с адаптацией к дереву. Вот что у меня есть:

Основа для моих деревьев:

abstract class GeoTree
case object EmptyTree extends GeoTree
case class Node(elem:GeoNode, left:GeoTree, right:GeoTree) extends GeoTree

Метод вставки для рекурсивного создания дерева (метод, вызывающий переполнение стека):

  def insert(t:GeoTree, v: GeoNode): GeoTree = t match {
    case EmptyTree => new Node(v, EmptyTree, EmptyTree)
    case Node(elem:GeoNode, left:GeoTree, right:GeoTree) => {
      if (v < elem) new Node(elem, insert(left, v), right)
      else new Node(elem, left, insert(right, v))
    }
  }

Я не думаю, что код дляGeoNode на самом деле особенно актуально, потому что это очень просто. В классе есть дваLong атрибуты и<, >, а также== операторы переопределяются соответствующим образом для использования внутри дерева. Может кто-нибудь сделать предложение о том, как использовать аккумулятор для моегоinsert функция, или какой-то другой способ сделать его рекурсивным?