再帰関数
自分自身を呼び出す関数.
問題を小さな部分問題に分割し、それらを解決するために同じ関数を再帰的に呼び出す方法.
末尾再帰
再帰呼び出しがその関数の最後で行われる特殊な形式.
再帰呼び出しが他に何もせずにただ返される形.
→いくつかのプログラミング言語では最適化が行われ、スタックの使用量を削減できる可能
コード例
階乗計算:
再帰関数
function(n)
if(n==1)
return 1
else
n*return function(n-1)
スタックの深さが増え続けると、スタックオーバーフローが発生し、プログラムが異常終了する可能。
末尾再帰関数
result=1
function(n,result)
if(n==0)
return result
else
return function(n-1,n*result)
スタックの使用を最小限に抑える効果がある(一部のプログラミング言語やコンパイラ)
C言語
C言語は末尾再帰関数を書けるが、最適化処理しない。スタックの使用量を削減するなどを実現できないはず。