Understanding Tail Recursion


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.

Deep Dive

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


Laisser un commentaire

Choisissez une méthode de connexion pour poster votre commentaire:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s