Structural recursion: recursive calls are made on structurally smaller arguments.
Tail recursion: the recursive call is the last thing that happens.
There is no requirement that the tail recursion should be called on a smaller argument. In fact, quite often tail recursive functions are designed to loop forever. For example, here's a trivial tail recursion (not very useful, but it is tail recursion):
def f(x):
return f(x+1)
We actually have to be a bit more careful. There may be several recursive calls in a function, and not all of them need to be tail recursive:
def g(x):
if x < 0:
return 42 # no recursive call
elif x < 20:
return 2 + f(x - 2) # not tail recursive
else:
return f (x - 3) # tail recursive
One speaks of tail recursive calls. A function whose recursive calls are all tail-recursive is then called a tail-recursive function.
