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

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.

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

我还有另一个问题.当我到达a时Leaf,返回的累加器始终为空.有人能解释我为什么会遇到这个问题吗？

Answer 1

常规提示:@tailrec注释可用于检查方法是否为尾递归.

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

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