Scala -递归方法返回不同的值

Question

我实现了一个计算来获得每个节点的节点评分。

计算该值的公式为:

• 子列表不能为空或标志必须为真;

迭代方法非常有效:

class TreeManager {
def scoreNo(nodes:List[Node]): List[(String, Double)] = {
  nodes.headOption.map(node => {
    val ranking = node.key.toString -> scoreNode(Some(node)) :: scoreNo(nodes.tail)
    ranking ::: scoreNo(node.children)
  }).getOrElse(Nil)
}
def scoreNode(node:Option[Node], score:Double = 0, depth:Int = 0):Double = {
  node.map(n => {
    var nodeScore = score
    for(child <- n.children){
      if(!child.children.isEmpty || child.hasInvitedSomeone == Some(true)){
        nodeScore = scoreNode(Some(child), (nodeScore + scala.math.pow(0.5, depth)), depth+1)
      }
    }
    nodeScore
  }).getOrElse(score)
}
}

但是在我用递归重构了这段代码之后，结果是完全错误的:

class TreeManager {
def scoreRecursive(nodes:List[Node]): List[(Int, Double)] = {
  def scoreRec(nodes:List[Node], score:Double = 0, depth:Int = 0): Double = nodes match {
    case Nil => score
    case n =>
      if(!n.head.children.isEmpty || n.head.hasInvitedSomeone == Some(true)){
        score + scoreRec(n.tail, score + scala.math.pow(0.5, depth), depth + 1)
      } else {
        score
      }
  }
  nodes.headOption.map(node => {
    val ranking = node.key -> scoreRec(node.children) :: scoreRecursive(nodes.tail)
    ranking ::: scoreRecursive(node.children)
  }).getOrElse(Nil).sortWith(_._2 > _._2)
}
}

节点是树的一个对象，它由下面的类表示:

case class Node(key:Int,
                children:List[Node] = Nil,
                hasInvitedSomeone:Option[Boolean] = Some(false))

下面是我运行来检查结果的部分:

object Main {
  def main(bla:Array[String]) = {
    val xx = new TreeManager
    val values = List(
      Node(10, List(Node(11, List(Node(13))),
        Node(12,
          List(
            Node(14, List(
              Node(15, List(Node(18))), Node(17, hasInvitedSomeone = Some(true)),
                Node(16, List(Node(19, List(Node(20)))), 
                  hasInvitedSomeone = Some(true))),
              hasInvitedSomeone = Some(true))),
          hasInvitedSomeone = Some(true))),
      hasInvitedSomeone = Some(true)))

    val resIterative = xx.scoreNo(values)
    //val resRecursive = xx.scoreRec(values)
    println("a")
  }
}

迭代的方式是工作的，因为我已经检查过了，但我不明白为什么递归返回错误的值。

任何想法?

提前感谢。

Answer 1

递归版本从不递归到节点的子节点上，只递归到尾部。而迭代版本既正确地递归子节点，又正确地迭代尾节点。

你会注意到你的"迭代"版本也是递归的。