4

私の記憶が正しければ、末尾再帰関数には常に簡単な非再帰関数があります。再帰には不要な関数呼び出しのオーバーヘッドが伴うため、非再帰的な方法で実行することをお勧めします。

この仮定は常に正しいですか？末尾再帰に賛成/反対する他の議論はありますか?

4

4 に答える 4

6

優れたコンパイラを備えた言語を使用している場合、これらのタイプの再帰を最適化して取り除くことができるため、再帰を使用することで読みやすさが向上する場合は、それを使い続けることをお勧めします。

于 2010-07-20T11:34:51.250 に答える
6

いいえ、必ずしもそうではありません。多くの言語やコンパイラは、末尾再帰呼び出しを簡単に最適化し、それを反復バージョンに書き換えたり、何らかの方法で後続の呼び出しにスタック フレームを再利用したりできます。

Scheme 言語では、実装でテール コールの最適化を採用することが義務付けられています

gcc はテール コールも最適化できます。リンク リスト内のすべてのノードを解放する関数を考えてみましょう。

void free_all(struct node *n)
{
    if(n != NULL) {
        struct node *next = n->next;
        free(n);
        free_all(next);
    }
}

コンパイルすると、最適化されます。

free_all:
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ebx
        subl    $20, %esp
        movl    8(%ebp), %eax
        testl   %eax, %eax
        je      .L4
        .p2align 4,,7
        .p2align 3
.L5:
        movl    4(%eax), %ebx
        movl    %eax, (%esp)
        call    free
        testl   %ebx, %ebx
        movl    %ebx, %eax
        jne     .L5
.L4:
        addl    $20, %esp
        popl    %ebx
        popl    %ebp
        ret

つまり、free_all を再帰的に呼び出す代わりの単純なジャンプです。

于 2010-07-20T11:36:03.640 に答える
2

いいえ。

読みやすさを求めてください。多くの計算は、再帰 (末尾またはその他) 関数としてより適切に表現されます。それらを回避する他の唯一の理由は、コンパイラが末尾呼び出しの最適化を行わず、呼び出しスタックを吹き飛ばす可能性があると予想される場合です。

于 2010-07-20T11:37:28.993 に答える
1

言語にもよりますが、多くの場合、オーバーヘッドはそれほど大きくありません。主観的かもしれませんが、再帰関数の方がはるかに理解しやすい傾向があります。ほとんどの場合、パフォーマンスの違いに気付かないでしょう。

私のプラットフォームがそれを処理するのが非常に苦手でない限り、私は末尾再帰を使用します (つまり、まったく処理を行わず、常にスタックにプッシュします)。

于 2010-07-20T11:34:19.860 に答える