A tail call is the last call executed in a function; if a tail call leads to the parent function being invoked again, then the function is tail recursive.
In the first function – foo; the baz() function is a tail call while in foo2, the baz and biz are tail calls because both are the last calls to get executed in the function. The second example shows that the tail call doesn’t have to be the last line of the function – it just has to be the last call the function makes before it returns.
Lets analyze the factorial function.
A fact(3) call is traced out below:
fact(3) -> 3 * fact(2)
3 * (2 * fact(1))
3 * (2 * 1)
3 * 2
Every recursive call has to be totally evaluated before the final value can be calculated.
Now let’s make a tail-recursive version of the same…
View original post 545 mots de plus