scala - 这个函数可以被认为是尾递归吗？

Question

这是我的功能：

    //Data Structures :
    abstract class HuffmanTree
  case class Node(left: HuffmanTree, right: HuffmanTree, chars: List[Char], weight: Int) extends HuffmanTree
  case class Leaf(char: Char, weight: Int) extends HuffmanTree


  def find_char(tree: HuffmanTree, x: Char, accu: List[Int]): (Boolean, List[Int]) = {
    tree match {
      case Leaf(c, _) => ((x == c),accu)
      case Node(left, right, ll, _) =>
      (find_char(left,  x,  accu ::: List(0))._1 || find_char(right, x,  accu :::List(1))._1, accu);
    }
  }

该函数采用霍夫曼树、字符和累加器。该函数的目的是在霍夫曼树中搜索字符并对其进行编码。所以我遍历树，当我向左时，我向累加器加 0，当我向右时，我向累加器加 1。

我想知道这个函数是否是尾递归的？

我还有另一个问题。当我到达 aLeaf时，返回的累加器总是空的。有人可以解释我为什么会遇到这个问题吗？

Answer 1

一般提示：@tailrec注解可用于检查方法是否为尾递归。

基本上在你的情况下，它不是尾递归：在这种情况下，两个递归调用之间Node有一个运算符。||

考虑到 的空列表Int。accu这很简单：在任何情况下都返回原始值。如果您find_char使用空列表作为第二个参数进行调用，则除了空列表之外，您无法获得其他内容。