21

foo(...) + foo(...)末尾再帰への最後の呼び出しとして「通常の」再帰を変換する一般的な方法があるかどうか疑問に思っていました。

例（スカラ）：

def pascal(c: Int, r: Int): Int = {
 if (c == 0 || c == r) 1
 else pascal(c - 1, r - 1) + pascal(c, r - 1)
}

再帰関数を同等の末尾呼び出しに変換する関数型言語の一般的な解決策:

簡単な方法は、非末尾再帰関数をTrampolineモナドでラップすることです。

def pascalM(c: Int, r: Int): Trampoline[Int] = {
 if (c == 0 || c == r) Trampoline.done(1)
 else for {
     a <- Trampoline.suspend(pascal(c - 1, r - 1))
     b <- Trampoline.suspend(pascal(c, r - 1))
   } yield a + b
}

val pascal = pascalM(10, 5).run

そのため、パスカル関数は再帰関数ではなくなりました。ただし、Trampoline モナドは、実行する必要がある計算のネストされた構造です。最後に、runツリーのような構造をたどって解釈し、最後に基本ケースで値を返す末尾再帰関数です。

トランポリンに関する Rúnar Bjanarson の論文: Stackless Scala With Free Monads

4

6 に答える 6

9

この質問がどれほど理論的かはわかりませんが、末尾再帰を使用しても再帰的な実装は効率的ではありません。pascal(30, 60)たとえば、 を計算してみてください。スタック オーバーフローが発生することはないと思いますが、長いコーヒー ブレークを覚悟してください。

代わりに、Streamまたはmemoizationの使用を検討してください。

val pascal: Stream[Stream[Long]] = 
  (Stream(1L) 
    #:: (Stream from 1 map { i => 
      // compute row i
      (1L 
        #:: (pascal(i-1) // take the previous row
               sliding 2 // and add adjacent values pairwise
               collect { case Stream(a,b) => a + b }).toStream 
        ++ Stream(1L))
    }))
于 2013-09-22T21:46:49.100 に答える
4

はい、可能です。通常、リストの長さをカウントするなど、いわゆるアキュムレータロジックを使用した追加の引数が1つある、内部的に定義された関数を介してアキュムレータパターンで行われます。

たとえば、通常の再帰バージョンは次のようになります。

def length[A](xs: List[A]): Int = if (xs.isEmpty) 0 else 1 + length(xs.tail)

これは末尾再帰バージョンではありません。最後の加算操作を排除するために、たとえばアキュムレータ パターンを使用して、何らかの方法で値を累積する必要があります。

def length[A](xs: List[A]) = {
  def inner(ys: List[A], acc: Int): Int = {
    if (ys.isEmpty) acc else inner(ys.tail, acc + 1)
  }
  inner(xs, 0)
}

コーディングにはもう少し時間がかかりますが、アイデアは明確だと思います。もちろん、内部関数なしで実行できますが、その場合はacc手動で初期値を指定する必要があります。

于 2013-09-22T15:09:46.657 に答える
3

一般的なケースを探している単純な方法では不可能であると確信していますが、変更をどれだけ複雑にするかによって異なります。

末尾再帰関数は while ループとして書き換え可能でなければなりませんが、while ループを使用してたとえばフラクタル ツリーを実装してみてください。可能ですが、配列またはコレクションを使用して各ポイントの状態を保存する必要があります。これは、コールスタックに保存されているデータの代わりになります。

トランポリンの使用も可能です。

于 2013-09-22T17:03:06.093 に答える
2

それは確かに可能です。私がこれを行う方法は、List(1) から始めて、必要な行に到達するまで繰り返し続けることです。最適化できることに注意してください: c==0 または c==r の場合、値は 1 であり、たとえば 100 行目の列 3 を計算するには、前の行の最初の 3 つの要素を計算するだけで済みます。動作する末尾再帰ソリューションは次のようになります。

def pascal(c: Int, r: Int): Int = {
  @tailrec
  def pascalAcc(c: Int, r: Int, acc: List[Int]): List[Int] = {
    if (r == 0) acc
    else pascalAcc(c, r - 1,
    // from let's say 1 3 3 1 builds 0 1 3 3 1 0 , takes only the
    // subset that matters (if asking for col c, no cols after c are
    // used) and uses sliding to build (0 1) (1 3) (3 3) etc.
      (0 +: acc :+ 0).take(c + 2)
         .sliding(2, 1).map { x => x.reduce(_ + _) }.toList)
  }
  if (c == 0 || c == r) 1
  else pascalAcc(c, r, List(1))(c)
}

注釈@tailrecは、関数が実際に末尾再帰的であることをコンパイラにチェックさせます。c > r/2 の場合、行が対称であることを考えると、おそらくさらに最適化される可能性があります。

于 2015-09-24T13:50:00.287 に答える