8

これらの言語は、相互再帰的な関数の最適化を「ネイティブに」サポートしていないので、トランポリンか、ループとして書き直す必要があると思います）何かが足りませんか？

更新：私はFSharpについて嘘をついたようですが、グーグル中に相互の末尾呼び出しの例を見ませんでした

4

3 に答える 3

10

まず、F＃はtailcall、.NET IL（MSDN）で利用可能な命令の恩恵を受けることができるため、相互再帰関数をネイティブにサポートします。ただし、これは少し注意が必要であり、.NETの一部の代替実装（コンパクトフレームワークなど）では機能しない可能性があるため、手動で対処する必要がある場合があります。

一般的に、私はそれに対処する方法がいくつかあると思います。

  • トランポリン-再帰の深さが高すぎる場合に例外をスローし、例外を処理するトップレベルのループを実装します（例外は呼び出しを再開するための情報を伝達します）。例外の代わりに、関数を再度呼び出す必要があることを指定する値を返すこともできます。

  • タイマーを使用して巻き戻します-再帰の深さが高すぎる場合は、タイマーを作成し、非常に短い時間の後にタイマーによって呼び出されるコールバックを指定します（タイマーは再帰を続行しますが、使用されているスタックは削除されます）。

    実行する必要のある作業を格納するグローバルスタックを使用して、同じことを実行できます。タイマーをスケジュールする代わりに、スタックに関数を追加します。トップレベルでは、プログラムはスタックから関数を選択して実行します。

最初の手法の具体例を示すために、F＃では次のように記述できます。

type Result<´T> =
  | Done of ´T
  | Call of (unit -> ´T)

let rec factorial acc n = 
  if n = 0 then Done acc
  else Call(fun () -> factorial (acc * n) (n + 1))

これは、相互再帰関数にも使用できます。命令ループは、最終結果が生成されるまで、にf格納されている関数を呼び出すだけです。これはおそらくこれを実装するための最もクリーンな方法だと思います。Call(f)Done

この問題に対処するための他の洗練されたテクニックがあると確信していますが、それらは私が知っている（そして私が使用した）2つです。

于 2010-05-09T19:21:46.393 に答える
8

Scala 2.8では、scala.util.control.TailCalls：

import scala.util.control.TailCalls._ 

def isEven(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty) 
    done(true) 
  else 
    tailcall(isOdd(xs.tail)) 

def isOdd(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty) 
    done(false) 
  else 
    tailcall(isEven(xs.tail)) 

isEven((1 to 100000).toList).result
于 2010-05-10T01:19:01.653 に答える
7

F＃相互再帰のためにBingを実行するときに、コードを手元に置いておくだけです。

let rec isOdd x =
    if x = 1 then true else isEven (x-1)
and isEven x = 
    if x = 0 then true else isOdd (x-1)

printfn "%A" (isEven 10000000)

これは、末尾呼び出しなしでコンパイルした場合はStackOverflowになりますが（「デバッグ」モードのデフォルト。これにより、スタックが保持され、デバッグが容易になります）、末尾呼び出しを使用してコンパイルした場合（「リリース」モードのデフォルト）は正常に実行されます。コンパイラはデフォルトで末尾呼び出しを行い（--tailcallsオプションを参照）、ほとんどのプラットフォームでの.NET実装はそれを尊重します。

于 2010-05-09T22:03:35.833 に答える