あまりにも多くの再帰なしでハフマンコードをデコード

Question

私はちょうどスカラを使用してハフマンコードを実装しました。しかし、私の関数の1つは大きなファイルではうまく機能しません。それは私があまりにも多くの再帰を使用するデコード機能、です：

def decode(tree: BinarySearchTree, bits: List[Boolean]): List[Char] = { 
    def searchCharactersInBinarySearchTree(t: BinarySearchTree, b: List[Boolean]): List[Char] = t match { 
    case LeafNode(ch, _) => if (b.isEmpty) List(ch) else ch :: searchCharactersInBinarySearchTree(tree, b) 
    case ForkNode(l, r, _, _) => if (b.head == false) searchCharactersInBinarySearchTree(l, b.tail) else searchCharactersInBinarySearchTree(r, b.tail) 
    } 
    searchCharactersInBinarySearchTree(tree, bits) 
} 

私は小さなビットは結構ですが、私のビットリストは（10000アイテム以上）大きい場合、それはStackOverflowのエラーをあげるリストアップしていた場合。私は、再帰を少なくして最適化できる場所を見つけることができません。私は問題が葉の再帰呼び出し（forkとは対照的）であることを知っています。

この再帰呼び出しを削除するにはどうすればよいのですか？一見

Answer 1

、あなたの実装がLeafNodeブランチで.tailが欠落しているので、あなたはLeafノードを打つたび、あなただけのbitsが縮小されていないので、何度も何度も同じ機能を呼び出しておきます。 tailrec注釈は、コンパイラのチェックを行う以外に何もしていないことを

def decode(tree: BinarySearchTree, bits: List[Boolean]): List[Char] = { 
    @scala.annotation.tailrec 
    def searchCharactersInBinarySearchTree(t: BinarySearchTree, b: List[Boolean], acc: List[Char] = Nil): List[Char] = t match { 
    case LeafNode(ch, _) => if (b.isEmpty) acc else searchCharactersInBinarySearchTree(tree, b.tail, ch :: acc) 
    case ForkNode(l, r, _, _) => if (b.head == false) searchCharactersInBinarySearchTree(l, b.tail) else searchCharactersInBinarySearchTree(r, b.tail) 
    } 
    searchCharactersInBinarySearchTree(tree, bits) 
} 

注方法は、実際にテールであること：それは安全な積み重ねだよう

第二に、あなたは、末尾再帰再帰関数を作ることができます - 再帰的。