Хвостовой рекурсивный метод максимальной глубины бинарного дерева в Scala - PullRequest
Новая
       67

Хвостовой рекурсивный метод максимальной глубины бинарного дерева в Scala

0 голосов
/ 21 апреля 2019

Я написал метод для расчета максимальной глубины двоичного дерева.

Я хотел бы написать хвостовой рекурсивный метод.

Я думал об использовании списков, но не нашел решения

Это мой метод, который не является хвостовым рекурсивным: 

def depth: Int = {

    def iter(f: FormulaWff): Int = f match {
      case Var(_) => 0
      case Not(e1) => 1 + iter(e1)
      case And(e1, e2)  => 1 + Math.max(iter(e1), iter(e2))
      case Or(e1, e2) => 1 + Math.max(iter(e1), iter(e2))
      case Implies(e1, e2) => 1 + Math.max(iter(e1), iter(e2))
    }

    iter(this)
  }

1 Ответ

1 голос
/ 21 апреля 2019

Попробуйте 

import scala.util.control.TailCalls.{TailRec, done, tailcall}

trait FormulaWff {
  def depth: Int = {
    def iter(f: FormulaWff): TailRec[Int] = {
      def hlp(e1: FormulaWff, e2: FormulaWff): TailRec[Int] = for {
        x <- tailcall(iter(e1))
        y <- tailcall(iter(e2))
      } yield 1 + Math.max(x, y)

      f match {
        case Var(_) => done(0)
        case Not(e1) => for {
          x <- tailcall(iter(e1))
        } yield 1 + x
        case And(e1, e2) => hlp(e1, e2)
        case Or(e1, e2) => hlp(e1, e2)
        case Implies(e1, e2) => hlp(e1, e2)
      }
    }

    iter(this).result
  }
}

case class Var(s: String) extends FormulaWff
case class Not(e: FormulaWff) extends FormulaWff
case class And(e1: FormulaWff, e2: FormulaWff) extends FormulaWff
case class Or(e1: FormulaWff, e2: FormulaWff) extends FormulaWff
case class Implies(e1: FormulaWff, e2: FormulaWff) extends FormulaWff

Прямое решение 

  sealed trait FormulaWff
  final case class Var(s: String) extends FormulaWff
  final case class Not(e: FormulaWff) extends FormulaWff
  final case class And(e1: FormulaWff, e2: FormulaWff) extends FormulaWff
  final case class Or(e1: FormulaWff, e2: FormulaWff) extends FormulaWff
  final case class Implies(e1: FormulaWff, e2: FormulaWff) extends FormulaWff

  sealed trait Result
  case object NotExpanded extends Result
  case object Expanded extends Result
  final case class Calculated(value: Int) extends Result

  final case class Frame(arg: FormulaWff, res: Result)

  def depth(f: FormulaWff): Int = step1(List(Frame(f, NotExpanded))) match {
    case Frame(arg, Calculated(res)) :: Nil => res
  }

  @tailrec
  def step1(stack: List[Frame]): List[Frame] = {
    val x = step(stack, Nil)
    x match {
      case Frame(arg, Calculated(res)) :: Nil => x
      case _ => step1(x)
    }
  }

  @tailrec
  def step(stack: List[Frame], acc: List[Frame]): List[Frame] = {
    stack match {
      case Frame(_, Calculated(res1)) :: Frame(_, Calculated(res2)) :: Frame(And(e1, e2), Expanded) :: frames =>
        step(frames, Frame(And(e1, e2), Calculated(1 + math.max(res1, res2))) :: acc)
      case Frame(_, Calculated(res1)) :: Frame(_, Calculated(res2)) :: Frame(Or(e1, e2), Expanded) :: frames =>
        step(frames, Frame(Or(e1, e2), Calculated(1 + math.max(res1, res2))) :: acc)
      case Frame(_, Calculated(res1)) :: Frame(_, Calculated(res2)) :: Frame(Implies(e1, e2), Expanded) :: frames =>
        step(frames, Frame(Implies(e1, e2), Calculated(1 + math.max(res1, res2))) :: acc)
      case Frame(_, Calculated(res1)) :: Frame(Not(e1), Expanded) :: frames =>
        step(frames, Frame(Not(e1), Calculated(1 + res1)) :: acc)
      case Frame(Var(s), _) :: frames =>
        step(frames, Frame(Var(s), Calculated(0)) :: acc)

      case Frame(Not(e1), NotExpanded) :: frames =>
        step(frames, Frame(Not(e1), Expanded) :: Frame(e1, NotExpanded) :: acc)
      case Frame(And(e1, e2), NotExpanded) :: frames =>
        step(frames, Frame(And(e1, e2), Expanded) :: Frame(e1, NotExpanded) :: Frame(e2, NotExpanded) :: acc)
      case Frame(Or(e1, e2), NotExpanded) :: frames =>
        step(frames, Frame(Or(e1, e2), Expanded) :: Frame(e1, NotExpanded) :: Frame(e2, NotExpanded) :: acc)
      case Frame(Implies(e1, e2), NotExpanded) :: frames =>
        step(frames, Frame(Implies(e1, e2), Expanded) :: Frame(e1, NotExpanded) :: Frame(e2, NotExpanded) :: acc)

      case Frame(arg, Expanded) :: frames => step(frames, Frame(arg, Expanded) :: acc)
      case Frame(arg, Calculated(res)) :: frames => step(frames, Frame(arg, Calculated(res)) :: acc)

      case Nil => acc.reverse
    }
  }

Как сделать отображение деревьев хвостовым рекурсивным?

...