再帰関数を末尾再帰に変換する

Question

循環二重リンクリストに値20を持つすべてのノードを数える次の再帰関数があります。安全性の問題を防ぐため、これを末尾再帰関数に変換する必要があります。同じように私を助けてください。おかげ

これは、一般的にそう実際にあなたを助けにはなりません末尾再帰フォームにあなたの関数を翻訳し、末尾再帰を認識しないC. Cの実装のように見えます

int count(node *start) 
{ 
    return count_helper(start, start); 
} 
int count_helper(node *current, node *start) 
{ 
    int c; 
    c = 0; 
    if(current == NULL) 
     return 0; 
    if((current->roll_no) == 20) 
     c = 1; 
    if(current->next == start) return c; 
    return (c + count_helper(current->next, start)); 
} 

Answer 1

。 iterativeに変更する必要があります。

Answer 2

非テール再帰関数をテール再帰関数に変換する一般的なアプローチは、再帰呼び出しによって現在の評価を保持する追加のアキュムレータパラメータを使用することです。あなたのケースでは

、これはかなりストレートフォワードです：

int count(node *start) 
{ 
    return count_helper(start, start, 0); 
} 
int count_helper(node *current, node *start, int acc) 
{ 
    int c; 
    c = 0; 
    if(current == NULL) 
     return acc; 
    if((current->roll_no) == 20) 
     c = 1; 
    if(current->next == start) return acc + c; 
    return count_helper(current->next, start, acc + c); 
} 

私がここで行われてきた主な変更は、あなたのcount_helper定義に余分なアキュムレータパラメータint accを追加し、return文のすべての確認を行っていますacc（該当する場合）が含まれます。最終的なreturnステートメントは、count_helperの結果を直接変更せずに戻します。これは現在、テール再帰的です。

再帰呼び出しの結果を単純な算術ではない方法で結合する必要がある場合はあまり簡単ではありません。

しかし、多くのCコンパイラはtail-recursive呼び出しを最適化するという頭痛に対処したくないというのは、単純にCのスタイルではないからです。多分-O3はそれを行うでしょうか？