HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMajor

Difference between Tail-Recursion and structural recursion

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
recursionstructuraldifferencetailbetweenand

Problem

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.

Solution

-
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 + 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.

Code Snippets

def f(x):
   return f(x+1)
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

Context

StackExchange Computer Science Q#85938, answer score: 28

Revisions (0)

No revisions yet.