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

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.

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 + f(x - 2)  # not tail recursive
  else:
     return f (x - 3)     # tail recursive

One speaks of tail recursive calls. A function whose all recursive calls are tail-recursive is then called a tail-recursice function.

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