Difference between Tail-Recursion and structural recursion

Question

Is there any difference between structural-recursion and Tail-recursion or they both are same? I see that in both of these recursions , the recursive function is called on the subset of the orignal items.

Answer 1

1. Structural recursion: recursive calls are made on structurally smaller arguments.

2. 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 + g(x - 2)  # not tail recursive (must add 2 after the call)
  else:
     return g(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.

Answer 2

Tail recursion is a very simple case of structural recursion, where the structure in question is a linked list. In the language you are probably using primarily, this list is probably not literally in the code; rather, it is a conceptual "list of calls to the function", a concept that may not be possible to express as written using that language. In Haskell (my language), any tail-recursive function call can actually be replaced by sequencing actions on a literal list whose elements literally are "calls to a function", but this is probably a functional-language thing.

Structural recursion is a way of operating on an object defined as a composite of other (possibly composite) objects. For example, a binary tree is an object containing references to two binary trees, or is empty (thus, it is a recursively defined object). Less self-referentially, a pair (t1, t2) containing two values of some types t1 and t2 admits structural recursion, although t1 and t2 need not also be pairs. This recursion takes the form

action on the pair = combination of the results of other actions on each element

which doesn't sound very profound.

It is often the case that a structural recursion cannot be tail-recursive, although any kind of recursion can be rewritten as a tail recursion (proof: if you run the original recursion, the actions are completed in a certain order; therefore, the recursion is equivalent to performing that particular sequence of actions, which as I discussed earlier, is tail recursion).

Either the binary tree or the pair example above demonstrate this: however you arrange the recursive calls on the subobjects, only one of them can be the last action; possibly neither one is, if their results are combined in some way (say, addition). As Andrej Bauer says in his answer, this can happen even with only one recursive call, as long as the result is modified. In other words, for every type of object other than those that are effectively linked lists (only one subobject all the way down), structural recursion is not tail recursion.