3

末尾呼び出しを除去するための再帰関数を常に構築できますか？そうでない場合、スタックサイズを制限する他の戦略は何ですか？

例:( ScalaのBreakまたはFoldの短絡に触発された）

// Depth-first search of labyrinth, with large depth > stacklimit
def search ( labyrinth: SearchDomain,
             path: List[SolutionNode],
             goal: DesiredResult ) = {

  if ( path.head == goal ) return path

  candidates: List[SolutionNode] = labyrinth.childNodes(path)

  candidates.find { c =>
    Nil != search( labyrinth, c :: path, goal ) // potential boom!
  } match {
    case Some(c) => c :: path
    case None => Nil
  }
}

目標は、この特定の機能を選択することではなく、スタックサイズを制限する手法を学ぶための小道具として使用することです。

アップデート

これからの私の持ち帰りは次のとおりです。

問題のドメインが、再帰がスタックサイズの制限に達する可能性があるようなものである場合：

コードを書き直して、scala-compiler-version-of-tailcall-optimizableにします。これは、新しい（2.8）@scala.annotation.tailrecアノテーションによって支援/検証できます。

それが不可能な場合は、反復ループ構造を使用するように書き直してください。

また、この書き直し（どちらの場合も）は、ある程度のスキル/才能/賢さ/練習が必要だと感じています。

4

4 に答える 4

9

すべての再帰関数は反復プロセスとして表現でき、すべての反復プロセスは末尾再帰として表現できるため、厳密に言えば、任意の再帰アルゴリズムを末尾再帰アルゴリズムに変換できます。ただし、これが実際にスペースを節約するとは思わないでください。多くの場合、スタックによる記録保持が必要であり、反復または末尾再帰バージョンで基本的にスタックをエミュレートする必要があります。これは、たとえば、スタックは小さいがヒープが大きい場合などに役立ちます。

于 2009-10-20T17:38:10.290 に答える
4

Laurence Gonsalvesの回答を受け入れる必要がありますが、コードに関しては:

// Depth-first search of labyrinth, with large depth > stacklimit
def search ( labyrinth: SearchDomain,
             path: List[SolutionNode],
             goal: DesiredResult ) = {
  if ( path.head == goal ) return path

  candidates: List[SolutionNode] = labyrinth.childNodes(path)

  candidates.find { c =>
    Nil != search( labyrinth, c :: path, goal ) // potential boom!
  } match {
    case Some(c) => c :: path
    case None => Nil
  }
}

になる

// Depth-first search of labyrinth
def search ( labyrinth: SearchDomain,
             path: List[SolutionNode],
             goal: DesiredResult ) = {
  def recurse( candidates: List[List[SolutionNode]],
               path: List[SolutionNode] ) = candidates match {
    case List(Nil) => Nil
    case Nil :: tail => recurse(tail, path.tail)
    case (nextCandidate :: otherCandidates) :: tail => 
      if (nextCandidate == goal)
        nextCandidate :: path
      else
        recurse(labyrinth.childNodes(nextCandidate :: path) :: otherCandidates,
                nextCandidate :: path)
  }

  if ( path.head == goal ) 
    path
  else
    recurse(labyrinth.childNodes(path), path)
}
于 2009-10-20T18:41:45.460 に答える
1

すべての再帰関数を末尾再帰として表現できるわけではないと思います。

ただし、すべての再帰関数を反復プロセスとして表現できます。

于 2009-10-20T17:21:59.933 に答える
1

ここで考慮すべき 2 つのケースがあります。一般的に、末尾呼び出しとして表現できない再帰関数はありますか? [更新]別の回答で指摘されているように、ありません。

ただし、scalaの特定のケースでは、末尾再帰的な方法で実行するように最適化できない末尾再帰関数がいくつかあります (スタック フレームを再利用することを意味します)。これは主に、私が信じている JVM の制限によるものです。

これがどのように機能するかについての詳細は、前の質問を参照してください。

于 2009-10-20T17:36:58.413 に答える