17

「再帰」を「末尾再帰」に変換する方法について質問があります。

これは宿題ではなく、アルゴリズムに関する本から再帰定理を磨こうとしたときに浮かんだ質問です。

私は、再帰を使用する 2 つの典型的な例 (階乗とフィボナッチ数列) に精通しており、再帰的な方法と末尾再帰的な方法でそれらを実装する方法も知っています。

私のコードは次のとおりです (単純にするために Perl を使用していますが、C/Java/C++ に簡単に変換できます)。

# This is the recursive function
sub recP {
    my ($n) = @_;
    if ($n == 0 or $n == 1 or $n == 2) {
        return 1;
    } else {
        return (recP($n-3) * recP($n-1)) + 1;
    }
}

for my $k (1 .. 10) {
    print "recP($k) = ", recP($k), "\n";
}

コードを実行すると、次のような出力が表示されます。

recP(1) = 1
recP(2) = 1
recP(3) = 2
recP(4) = 3
recP(5) = 4
recP(6) = 9
recP(7) = 28
recP(8) = 113
recP(9) = 1018

再帰関数は、戻る前に異なるパラメーターで 2 回自身を呼び出します。これを末尾再帰関数に変換する方法をいくつか試しましたが、すべて間違っていることが判明しました。

誰でもコードを見て、末尾再帰にする正しい方法を教えてもらえますか? 特に、このツリー再帰の変換のためのルーチンがあると思います(戻る前に再帰関数を複数回呼び出す)、誰かがこれに光を当てることができますか? そのため、同じロジックを使用して、後でさまざまな質問を処理できます。

4

5 に答える 5

23

階乗を末尾呼び出しに変換する例として、次のことがよく見られます。

int factorial(int n, int acc=1) {
  if (n <= 1) return acc;
  else        return factorial(n-1, n*acc);
}

乗算は結合法則と可換法則の両方である必要があるため、これは完全には正しくありません。（乗算は結合法則と可換法則ですが、上記はこれらの制約を満たさない他の演算のモデルとしては機能しません。）より良い解決策は次のとおりです。

int factorial(int n, int k=1, int acc=1) {
  if (n == 0) return acc;
  else        return factorial(n-1, k+1, acc*k);
}

これは、フィボナッチ変換のモデルとしても機能します。

int fibonacci(int n, int a=1, int b=0) {
  if (n == 0) return a;
  else        return fibonacci(n-1, a+b, a);
}

これらは、呼び出しスタックで保留中の継続をキューに入れるのではなく、最初からシーケンスを計算することに注意してください。したがって、それらは、再帰的なソリューションというよりも、構造的に反復的なソリューションに似ています。ただし、反復プログラムとは異なり、変数を変更することはありません。すべてのバインディングは一定です。これは面白くて便利なプロパティです。これらの単純なケースでは、大きな違いはありませんが、再割り当てなしでコードを記述すると、一部のコンパイラの最適化が容易になります。

とにかく、最後のものは再帰関数のモデルを提供します。フィボナッチ数列のように、関連する過去の値を保持する必要がありますが、2つではなく3つが必要です。

int mouse(int n, int a=1, int b=1, int c=1) {
  if (n <=2 ) return a;
  else        return mouse(n-1, a*c+1, a, b);
}

補遺

コメントでは、2つの質問が提起されました。ここでそれら（およびもう1つ）に答えようとします。

まず、（関数呼び出しの概念を持たない基盤となるマシンアーキテクチャを考慮して）、関数呼び出しをgoto（おそらく非制限の中間ストレージを使用）と言い換えることができることを明確にする必要があります。さらに、どのgotoも末尾呼び出しとして表現できます。したがって、再帰を末尾再帰として書き直すことは可能です（ただし、必ずしもきれいである必要はありません）。

通常のメカニズムは「継続渡しスタイル」です。これは、関数を呼び出すたびに、代わりに現在の関数の残りを新しい関数（「継続」）としてパッケージ化し、それを渡すという派手な言い方です。呼び出された関数への継続。その後、すべての関数は引数として継続を受け取るため、受け取った継続の呼び出しで作成した継続を終了する必要があります。

おそらく頭を回転させるのに十分なので、別の言い方をします。引数と戻り位置をスタックにプッシュして関数（後で戻る）を呼び出す代わりに、引数と継続位置をスタックにプッシュします。そして、関数に移動します。この関数は、後で継続位置に移動します。つまり、スタックを明示的なパラメータにするだけで、戻る必要はありません。このスタイルのプログラミングは、イベント駆動型コード（Python Twistedを参照）では一般的であり、書き込み（および読み取り）するのは非常に困難です。したがって、コンパイラーにこの変換を実行させることを強くお勧めします。

@xxmouseは、私が漸化式を帽子から引き抜くことを提案し、それがどのように導き出されたかを尋ねました。これは単に元の再帰ですが、単一のタプルの変換として再定式化されています。

fn = fn-1*fn-3 + 1
=>
Fn = <Fn-11*Fn-13+1, Fn-11, Fn-12>

それがもっと明確かどうかはわかりませんが、私ができる最善のことです。少し単純なケースについては、フィボナッチの例を見てください。

@j_random_hackerは、この変換の制限を尋ねます。kこれは、各要素が前の要素の式で表すことができる再帰シーケンスで機能します。ここkで、は定数です。末尾呼び出しの再帰を生成する方法は他にもあります。例えば：

// For didactic purposes only
bool is_odd(int n) { return n%2 == 1; }

int power(int x, int n, int acc=1) {
  if (n == 0)         return acc;
  else if (is_odd(n)) return power(x, n-1, acc*x);
  else                return power(x*x, n/2, acc);
}

上記は、通常の非末尾呼び出し再帰と同じではありません。これは、異なる（ただし同等で同じ長さの）乗算シーケンスを実行します。

int squared(n) { return n * n; }

int power(int x, int n) {
  if (n == 0)         return 1;
  else if (is_odd(n)) return x * power(x, n-1));
  else                return squared(power(x, n/2));
}

次のテストを行ってくれたAlexeyFrunzeに感謝します。出力（ideone）：

mouse(0) = 1
mouse(1) = 1
mouse(2) = 1
mouse(3) = 2
mouse(4) = 3
mouse(5) = 4
mouse(6) = 9
mouse(7) = 28
mouse(8) = 113
mouse(9) = 1018
于 2013-03-21T05:33:27.837 に答える
6

Google を使用して、Tail Recursionについて説明しているこのページを見つけました。基本的に、関数を少なくとも 2 つの他の関数に分割する必要があります。1 つは作業を行い、現在の値の「累積」を保持し、もう 1 つはワークハウス関数のドライバーです。C の階乗の例は次のとおりです。

/* not tail recursive */
unsigned int
factorial1(unsigned int n)
{
    if(n == 0)
        return 1;
    return n * factorial1(n-1);
}

/* tail recursive version */
unsigned int 
factorial_driver(unsigned int n, unsigned int acc)
{
    if(n == 0)
        return acc;

    /* notice that the multiplication happens in the function call */
    return factorial_driver(n - 1, n * acc);
}

/* driver function for tail recursive factorial */
unsigned int
factorial2(unsigned int n)
{
    return factorial_driver(n, 1);
}
于 2013-03-21T00:48:38.583 に答える
3

@Alexey Frunzeの答えは大丈夫ですが、正確には正しくありません。プログラムを継続渡しスタイルに変換することにより、すべての再帰が末尾再帰であるプログラムに変換することは確かに可能です。

今は時間がありませんが、数分あればCPSでプログラムを再実装しようとします。

于 2013-03-21T05:40:46.657 に答える
1

問題は、最後の演算が再帰呼び出しの 1 つではなく、乗算に 1 を加算することです。C での関数:

unsigned faa (int n)  // Ordinary recursion
{
    return n<3 ? 1 :
                 faa(n-3)*faa(n-1) + 1;  // Call, call, multiply, add
}

値が要求される順序を変更すると、呼び出しの 1 つをループにすることができます。

unsigned foo (int n)  // Similar to tail recursion
{                     // (reverse order)
    int i;
    unsigned f;

    for (i=3, f=1; i<=n; i++)
        f = f*foo(i-3) + 1;

    return f;
}

重要なのは、値が要求された順序ではなく、元の関数で実際に計算された順序について考えることです。

1 つの再帰呼び出しを削除したいと想定していることに注意してください。コンパイラが最適化することを期待して関数の最後に再帰呼び出しを書きたい場合は、他の回答を参照してください。

ただし、ここで行うべき「正しいこと(TM)」は、動的計画法を使用して、同じ値を何度も計算しないようにすることです。

unsigned fuu (int n)  // Dynamic programming
{
    int i;
    unsigned A[4]={1,1,1,1};

    for (i=3; i<=n; i++)
    {
        memmove (A+1, A, 3*sizeof(int));
        A[0] = A[1]*A[3] + 1;
    }

    return A[0];
}

配列 A には、シーケンスのスライディング ウィンドウが含まれます: A[0]==f(i)、A[1]==f(i-1)、A[2]==f(i-2) など.

次のmemmoveように書かれている可能性があります。

        A[3] = A[2];
        A[2] = A[1];
        A[1] = A[0];
于 2013-03-21T06:34:40.190 に答える