這個函數可以被認爲是尾遞歸嗎？

這裏是我的功能：這個函數可以被認爲是尾遞歸嗎？

//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時，返回的累加器總是空的。有人可以解釋我爲什麼有這個問題嗎？

來源

2012-10-18 Dimitri

我回答了第一部分。您的代碼目前包含語法錯誤。因此很難說出它有什麼問題。 – Nicolas

只需糾正語法錯誤。對於第二部分，返回累積器是空的。 – Dimitri

最後一行仍然有一個括號不匹配。如果我理解得很好，你的問題就來自它。你能複製/粘貼你的實際代碼嗎？ – Nicolas

一般提示：可以使用@tailrec註釋來檢查方法是否是遞歸的。

基本上在你的情況下，這是不是尾遞歸：在Node情況下，有兩個遞歸調用之間的||操作。

考慮到空列表Int。很簡單：無論如何你都會返回原始值accu。如果您使用空列表作爲第二個參數調用find_char，則不能獲得除空列表之外的其他內容。

來源

2012-10-18 12:47:57 Nicolas

即使我在遞歸調用中更新累加器值？ – Dimitri

列表是不可變的。沒有副作用。你不會「更新」累加器。你創建一個**新的**，使用原始的和一個元素的列表。 – Nicolas

通過更新，我的意思是添加一個新元素到列表中，我完全明白這一點。但是我通過在累加器中添加一個新元素來進行遞歸調用。所以當我到達時，累加器在遍歷樹時必須全部爲0和1。不是嗎？ – Dimitri

這個函數可以被認爲是尾遞歸嗎？

回答

相關問題