1

ここに私の機能があります:

    //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 を追加します。

この関数が末尾再帰的かどうかを知りたいですか?

また、別の問題があります。に到達するLeafと、返されるアキュムレータは常に空です。誰かが私にこの問題がある理由を説明できますか?

4

1 に答える 1

11

一般的なヒント:@tailrec注釈を使用して、メソッドが末尾再帰的かどうかを確認できます。

基本的にあなたの場合、末尾再帰ではありません。このNode場合、||2 つの再帰呼び出しの間に演算子があります。

の空のリストを考慮しますInt。それは簡単です: どのような場合でも の元の値を返しますaccu。空のリストを 2 番目のパラメーターとして呼び出しfind_charた場合、空のリスト以外のものを取得することはできません。

于 2012-10-18T12:47:57.497 に答える