Tail calls are the last functions called in a parent function, often returning a value which is immediately returned by the parent function.
def any_old_function():
# ...
# do anything
# ...
return some_other_function() # this is a tail call!
def recursive_function(n):
# do anything...
# preferably something that terminates...
if n == 0:
return 42
return recursive_function(n - 1) # this is a tail recursion call!
Watch python barf because it has a maximum stack limit:
How about 5000?
RuntimeError: maximum recursion depth exceeded
Python has a default hard limit on stack size:
>>> import sys
>>> sys.getrecursionlimit()
1000
Why is knowing if something is a Tail Call important? Normally, calling a function involves adding a new stack frame to the call stack. Every function call, you say, “OK, leaving the current stack frame on the stack, let’s add another frame on top”. This is part of the overhead involved with calling many functions.
BUT! If you know your new function call is a tail call, you can recycle or replace the top stack frame, since you know most of the frame of the last function won’t be needed. This is known as tail call elimination or tail call optimization (but certain people will rage if you call it optimization, because they think it’s so important in functional languages).
You will find tail call elimination in most functional languages like ML, Scheme, Haskell, Clojure (with some cajoling)—and even Perl (though you specify tail calls manually).