最後の再帰は何ですか.効率が非常に高い

この文章は回ってきた.https://www.cnblogs.com/zhanggui/p/7722541.html
テール再帰を理解する前に、テールコールを理解してください.

function foo(data) {
    a(data);
    return b(data);
}

ここでのa(data)とb(data)はいずれも関数呼び出しであるが、b(data)は関数が戻る前の最後に実行されるものであるため、いわゆる末尾位置でもある.例:

function foo1(data) {
    return a(data) + 1;
}
function foo2(data) {
    var ret = a(data);
    return ret;
}
function foo3(data) {
    var ret = a(data);
    return (ret === 0) ? 1 : ret;
}

これはエンドコールではなく、foo 1の場合、最後の動作は+1操作であり、直接関数呼び出しではない.foo 3の場合、計算によって返された結果であり、エンドコールでもない.foo 2もテールコールではありません
テールコールの重要な特性は、呼び出しスタックに新しいスタックフレームを追加するのではなく、更新することです.
次に、末尾再帰とは何かを説明します.
1つの関数が末尾位置で自身(または1つの末尾呼び出し自体の他の関数など)を呼び出す場合、この場合を末尾再帰と呼び、再帰の特殊な状況である.形式的には、最後のreturn文が完全な関数を返す限り、最後の再帰です.ここで、テールコールは必ずしも再帰コールではありませんが、テール再帰は必ずテールコールです.
次に,フィボナッチ数列と階乗により尾再帰の意味をさらに理解する.
フィボナッチ数列
従来のフィボナッチ数列アルゴリズムは、次のようになります.

int fib(int n) {
 
    if (n <= 2) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

上記のような再帰計算の最終的なreturn動作は加算動作である.だから尾再帰ではありません.
末尾再帰を使用すると、次のようになります.

/**
    n         
  
 @param n  n  
 @param acc1  n  
 @param acc2  n  n+1    
 @return          
 */
int tailfib(int n,int acc1,int acc2) {
    if (n < 2) {
        return acc1;
    }
     
    return tailfib(n-1,acc2,acc1 + acc2);
}

 
例えば,10番目のフィボナッチ数列の値を計算するにはfib(10,1,1)だけでよい.
テストの効果を見てみましょう.テスト手順は以下の通りです.

int main(int argc, const char * argv[]) {
    clock_t start,finish;
    
    start = clock();
    printf("    ：%d
", fib(45));
    finish = clock();
    printf("    --------%lu
",finish - start);
 
     
    start = clock();
    printf("    ：%d
", tailfib(45,1,1));
    finish = clock();
     
    printf("    --------%lu
",finish - start);
    return 0;
     
}

計算結果は次のとおりです.

    ：1134903170
    --------5540692
    ：1134903170
    --------4
Program ended with exit code: 0

効率的には,尾再帰はローリング普通再帰と言える.
 
階乗
通常の階乗の計算方法は、次のようになります.

int fac(int n) {
    if (n == 1) {
        return 1;
    }
    return fac(n-1) * n;
}

複雑度O(n)
テール再帰アルゴリズムは次のとおりです.

int tailfac(int n,int sum) {
    if (n == 1) {
        return sum;
    }
    return fac(n-1, n * sum);
}

複雑度O(1)
効率をテストします.テスト手順は次のとおりです.

int main(int argc, const char * argv[]) {
    clock_t start,finish;
    
    start = clock();
    printf("    ：%d
", fac(16));
    finish = clock();
    printf("    --------%lu
",finish - start);
 
     
    start = clock();
    printf("    ：%d
", tailfac(16,1));
    finish = clock();
     
    printf("    --------%lu
",finish - start);
    return 0;
     
}

テスト結果:

    ：2004189184
    --------31
    ：2004189184
    --------2
　　

テール再帰効率は高いですが、個人的にはテール再帰アルゴリズムが理解しにくいと思います.各入力パラメータの役割をマークする必要があります.そうしないと、接触したばかりで必ずしもこのアルゴリズムを使うとは限りません.