尻尾

3280 ワード

🤔 尻尾の耳は何ですか。


アルゴリズムを学ぶときに尻尾再帰についての内容を整理します.
通常の再帰関数は、関数を呼び出し続けるため、スタック領域にあります.
関数が蓄積されます.

(写真は下の関数と違います!)

尻尾はかわいいですか?


再帰呼び出しが終了した後に現在の関数が追加演算を必要としない再帰を実現

このように積み重ねる必要はありません.1つのスタックに書き続けるだけです.

コードで調べてみます.
public int  Factorial(int n){
    if(n == 1) return 1;
    return n * Factorial(n-1);

} // 일반 재귀함수

public int Tail(int n, int acc){
    if(n == 1) return acc;
    return Tail(n-1, n * acc);
}

public void main(){
    Tail(n, 1);
} // 꼬리재귀
Tail関数は追加の演算を必要とせず、コンパイラは自分で末尾再帰として処理します.