テール再帰と通常再帰でnを実現!アルゴリズム、両者比較

尾再帰−Tail Recursion尾再帰は従来の再帰アルゴリズムに対して行われており,従来の再帰アルゴリズムは多くの場合洪水猛獣と見なされている.その名声は狼籍で、永遠に低効と結びついているようだ.末尾再帰とは最後から計算するものであり、再帰ごとに相応の結果が出る、すなわち、関数呼び出しは呼び出し者の関数の末尾に現れるが、末尾であるため、局所変数を保存する必要はない.呼び出された関数を返すときに呼び出し者を越えて呼び出し者の呼び出し者に直接返す.n!例として説明するが、後の例n=5.
コード線形再帰

int Rescuvie(int n)
{      
  return(n == 1) ? 1 : n * Rescuvie(n - 1);      
}     

テール再帰

int TailRescuvie(int n, int a) 
{      
  return(n == 1) ? a : TailRescuvie(n - 1, a * n);        
}      

int TailRescuvie(long n)   //      
{  
  return(n == 0) ? 1 : TailRescuvie(n, 1);    
}  

プロセス
リニア再帰
Rescuvie(5){5*Rescuvie(4)}{5*{4*Rescuvie(3)}{5*{4*{4*{4*{3*Rescuvie(2)}{5*{4*{4*{3*{3*{2*Rescuvie(1)}}{5*{4*{3*{2*1}}{5*{4*{4*{4*{3*2}{5*{4*6}{5*{4*6}{5*24}120尾再帰TailRescuvie(5)TailRescuvie(5,1)TailRescuvie(5,1)TailRescuvie(5,1)TailRescuvie(5,1)Tailcuvie(1)4,5)TailRescuvie(3,20)TailRescuvie(2,60)TailRescuvie(1,120)120
結論:通常の線形再帰はテール再帰よりもリソースを消費し、実装上は、繰り返しのプロセス呼び出しのたびに呼び出しチェーンが長くなり、システムはスタックを使用してデータ保存とリカバリを行わなければならない.尾再帰にはこのような問題は存在しない.彼の状態は完全にnとaによって保存されているからだ.
深く入り込む
コンパイラはどのように尾再帰を最適化しますか?再帰呼び出しはスタックによって実現されることを知っています.関数を呼び出すたびに、システムは関数の現在の変数、戻りアドレスなどの情報をスタックフレームとしてスタックに圧入します.そうすると、処理する演算が大きくなったり、データが多くなったりすると、多くの関数呼び出しや大きなスタックフレームを引き起こす可能性があります.このように、スタックを圧入し続けると、スタックのオーバーフローを招きやすいです.最後の再帰の特性を振り返ってみると、関数は再帰呼び出しの前にすべての計算タスクを完了しています.彼は得られた結果をすべてサブ関数に渡せばいいので、何も保存する必要はありません.サブ関数は実際にスタックフレームを作成する必要はありません.直接現在のスタックフレームについて、元のデータを上書きすればいいです.対照的に、通常の再帰であれば、関数は再帰呼び出しの前にすべての計算を完了していないし、return n*fact(n-1)のような再帰関数を呼び出して完了してから演算タスクを完了する必要がある.このfact(n)は、fact(n−1)を計算した後にn*fact(n−1)の演算結果を得てから返される.以上のように、コンパイラのテール再帰の最適化は、実際には、テール再帰を行うときに、新しいスタックフレームを作成するのではなく、現在のスタックフレームを上書きすることで、スタックオーバーフローを防止し、関数を呼び出すときにスタックフレームを作成するオーバーヘッドを節約することです.
最適化作業はコンパイラに任せますか、それとも自分に任せますか.ネット上で調べたところ、java、C#、pythonはコンパイル環境の自動最適化テール再帰をサポートしていない.この場合、もちろん再帰を使用しないほうが効率が高い.しかし、C言語にとって、コンパイラが白で提供するサービスは、使っても悪くない.結局、再帰コードは少し理解できるが、言い換えれば、末尾再帰と書くと、非再帰になるのはよく実現され、完全にループで解決できる(末尾再帰は一般的にループ文に変換できる).だからこの时、个人の好みを见ました.
参照:http://site.douban.com/196781/widget/notes/12161495/note/262014367/