Tail recursion has the following form:
def func(x..., value){
if(condition) return value
else func(y..., value')
}
If you look at this form, what you see is that in order to evaluate func
all I need is func
itself but with a different set of arguments. Therefore, there is only one item to be placed on the stack and it can easily be transformed into an iterative algorithm.
What you've implemented looks like this:
def func(x...){
if(condition) return value
else func(y...) + func(z...)
Notice that in order to evaluate func
that you must first evaluate func
, an operator +
and then 'func' again. So that's 3 items that need to be placed on the stack with a very real order of evaluation which is not amenable to tail call optimization.