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

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); 
    } 
    } 

功能需要一个哈夫曼树，字符和累加器。该函数的目的是搜索huffman树中的字符并对其进行编码。所以我遍历树，当我向左走时，我向累加器加0，当我向右走时，我向累加器加1。

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

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

Answer 1

一般提示：可以使用@tailrec注释来检查方法是否是递归的。

基本上在你的情况下，这是不是尾递归：在Node情况下，有两个递归调用之间的||操作。

考虑到空列表Int。很简单：无论如何你都会返回原始值accu。如果您使用空列表作为第二个参数调用find_char，则不能获得除空列表之外的其他内容。