Why is quick sort called a tail recursive algorithm?

Question

I know what a tail recursive algorithm is as written out in this SO answer. However I am going through this video of quick sort algorithm from MIT and at 18:30 seconds the professor says that this is tail recursive algorithm. I fail to connect how this is tail recursive . We are not doing calculation at any step of recursion or are we ? Can you explain why this is cited as an example of tail recursive algorithm . Please base your answer on the premise that I know what an recursive algorithm is . The part that isn't clear to me is why it is called tail recursive ?

Answer 1

Tail recursion is not about calculating in steps. It is about "the recursion could be evaluated without building call stack." The example given by What is tail recursion? is an special caseof this. If you look the example more deeply, what you can find is that

def recsum(x):
 if x==1:
  return x
 else:
  return x+recsum(x-1)

1) to run the above code successfully, you need to build the call stack. But,

def tailrecsum(x,running_total=0):
  if x==0:
    return running_total
  else:
    return tailrecsum(x-1,running_total+x)

2) to run the above code, you don't need to build the call stack because of running_total. Just build the call stack for the "original call" and for the recursion, no need to build call stack, because the status required to evaluate this function is stored in running_total.

And, about the quick-sort, I think the professor probably meant that quick-sort could be optimized by "using" tail-recusion. For the two branching parts of qsort(), we can use tail-recursion on one side that has higher items (based on pivot position).

Answer 2

Have a look at the wiki page of Quicksort. There is a version of tail recursive

 function quicksort(array, 'left', 'right')

  // If the list has 2 or more items
  if 'left' < 'right'

      // See "Choice of pivot" section below for possible choices
      choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right'

      // Get lists of bigger and smaller items and final position of pivot
      'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex')

      // Recursively sort elements smaller than the pivot
      quicksort(array, 'left', 'pivotNewIndex' - 1)

      // Recursively sort elements at least as big as the pivot
      quicksort(array, 'pivotNewIndex' + 1, 'right')

According to the definition of Tail recursion, the last method call of quicksort is itself, that's tail recursion. But some other implementations are not tail recursive.

 quicksort(left) + pivot + quicksort(right)

Because the final action in quicksort is sorted_left + pivot + sorted_right