2

重複の可能性:
C++ の末尾再帰

私はC ++での末尾再帰が初めてです。私のプロジェクトでは、すべての関数を末尾再帰にする必要があります。次のコードをテストしましたが、正しく動作します。ただし、どのように実行したかは、末尾再帰としての資格があるかどうかはわかりません。

static int sum_helper(list_t hList, int accumulator){
    if (list_isEmpty(hList))
        return accumulator;
    else {
        accumulator += list_first(hList);
        hList = list_rest(hList);
        return sum_helper(hList, accumulator); 
    }
}

int sum(list_t list){
/* 
 // EFFECTS: returns the sum of each element in list
 //          zero if the list is empty.
 */
    if (list_isEmpty(list))
        return 0;
    return sum_helper(list, 0);
}

ありがとう！

4

3 に答える 3

2

つまり、再帰呼び出し ( ) の後は何もしませんsum_helper。つまり、呼び出し元に戻る必要がないため、呼び出し元のスタック フレームを破棄できます。

通常の階乗関数の例を見てみましょう

int fact(int x)
{
    if(x == 0)
        return 1;
    else
        return x * fact(x-1);
}

fact(x-1)の値を返してから 6 を掛ける必要があるため、これは末尾再帰ではありません。代わりに、少しごまかして、アキュムレータも渡すことができます。これを参照してください：

int fact(int x, int acc)
{
     if(x == 0)
         return acc;      // Technically, acc * 1, but that's the identity anyway.
     else
         return fact(x-1, acc*x);
}

ここで、制御フローの最後の関数呼び出しは ですfact(x-1, acc*x)。その後、呼び出された関数の戻り値を他の目的で使用する必要がないため、現在のフレームに戻る必要はありません。このため、スタック フレームを破棄して、他の最適化を適用できます。

免責事項：階乗アルゴリズムを間違って適用した可能性がありますが、要点はわかります。うまくいけば。

于 2012-09-23T23:09:25.560 に答える
2

list_t に非自明なデストラクタがない場合、これは末尾再帰です。自明でないデストラクタがある場合、デストラクタは、再帰呼び出しが戻った後、関数自体が戻る前に実行する必要があります。

ボーナス：

int sum(list_t hList, int accumulator = 0) {
return list_isEmpty(hList)
    ? 0
    : sum(list_rest(hList), accumulator + list_first(hList));
}

しかし、好みはさまざまです。あなたのほうが好きな人もいるかもしれません。

于 2012-09-23T23:14:16.070 に答える
1

理論的な観点からは、そうです、これは末尾再帰です (hList に非自明なデストラクタがない場合)。しかし、実用的な観点からは、コンパイラとその設定に依存します。この単純なコード用に生成されたアセンブリを見てみましょう。

#include <cstdlib>

struct list{
   int head;
   list * tail;
};


int sum_helper(list * l, int accumulator){
    if (l == NULL)
        return accumulator;
    else {
        accumulator += l->head;
        return sum_helper(l->tail, accumulator); 
    }
}

最適化ON : (g++ -O2 ...、退屈な部分は省略):

    testq   %rdi, %rdi
    movl    %esi, %eax
    je  .L2
    ...
.L6:
    ...
    jne .L6                  <-- loop
.L2:
    rep
    ret

これは明らかにループです。しかし、最適化を無効にすると、次のようになります。

_Z10sum_helperP4listi:
.LFB6:
    ...
    jne .L2
    movl    -12(%rbp), %eax
    jmp .L3
.L2:
    ...
    call    _Z10sum_helperP4listi     <-- recursion
.L3:
    leave
    .cfi_def_cfa 7, 8
    ret

これは再帰的です。

于 2012-09-23T23:26:32.700 に答える