9
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ What research did you do? What is your understanding of tail recursion? Why do you think it's similar to structural recursion? $\endgroup$ – Jonathan Cast Dec 26 '17 at 14:25
  • $\begingroup$ Any chance you could add what you saw that made you think they might be same or very similar? It might help instructors clarify it when teaching the concepts to people. $\endgroup$ – Mehrdad Dec 27 '17 at 0:31
29
$\begingroup$
  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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It is false that tail recursion is only about lists, imagined or real. It is perfectly possible to have tail recursion over binary trees, for example. I can see why someone would think it is because the rest of the list is its "tail". $\endgroup$ – Andrej Bauer Dec 27 '17 at 13:46
  • $\begingroup$ @AndrejBauer I will feel suitably embarrassed about this when I understand exactly what's wrong. It seems tautological that tail recursion of the form f x = (stuff defining x'); f x'is the same as the sequencing of nodes in a linked list defined like l = modify f : l(in Haskell state-monad style). It wasn't just the terminological similarity for me. As for tail recursion over binary trees, could you elaborate? I can only think of the linearization fact from my second-last paragraph. $\endgroup$ – Ryan Reich Dec 27 '17 at 23:31
  • $\begingroup$ Not all tail-recursive calls are of that form. For instance, there can be several tail recursive calls in different branches (of case statements, or some such). It's more natural to think of those as selecting a path through a tree. Also note that the calls are tail recursive (or not), so you could have f (f x) where the outer call of f is tail-recursive. How does that fit into the view that it's all about lists? Here's another example: f : (Int -> Int) -> (Int -> Int) with f g 0 = g 42 and f g (n + 1) = f (f . g) n. The possibilities are endless, and some are useful. $\endgroup$ – Andrej Bauer Dec 27 '17 at 23:58
  • $\begingroup$ @AndrejBauer The question was about tail recursion rather than just tail calls, so I would not consider the f (f x) applicable: in the evaluation of the outer f, the inner one is not a tail call (unless f is the identity). If-statements can be trivially rewritten not to branch in the tail call: if (c) then f a else f b == let x = if (c) then a else b in f x. The last example is invalid because f . g doesn't typecheck; even so, it would still not be tail recursion: f g = \n -> if n == 0 then g 42 else f (f . g) (n - 1) is not a call to f, but a genuinely different lambda. (next) $\endgroup$ – Ryan Reich Dec 28 '17 at 5:50
  • $\begingroup$ I'd actually say that example is of mutual tail recursion, i.e. f g = h where { h 0 = g 42; h n = f (f . g) (n - 1) }, but if you bring that into the discussion, then any recursive function, tail or not, is admissible and the term becomes meaningless. $\endgroup$ – Ryan Reich Dec 28 '17 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.