Tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call. For example, the function

int f(int x, int y) {
  if (y == 0) {
    return x;
  }

  return f(x*y, y-1);
}

is tail recursive (since the final instruction is a recursive call) whereas this function is not tail recursive:

int g(int x) {
  if (x == 1) {
    return 1;
  }

  int y = g(x-1);

  return x*y;
}

since it does some computation after the recursive call has returned.

Tail recursion is important because it can be implemented more efficiently than general recursion. When we make a normal recursive call, we have to push the return address onto the call stack then jump to the called function. This means that we need a call stack whose size is linear in the depth of the recursive calls. When we have tail recursion we know that as soon as we return from the recursive call we're going to immediately return as well, so we can skip the entire chain of recursive functions returning and return straight to the original caller. That means we don't need a call stack at all for all of the recursive calls, and can implement the final call as a simple jump, which saves us space.

Simply said, tail recursion is a recursion where the compiler could replace the recursive call with a "goto" command, so the compiled version will not have to increase the stack depth.

Sometimes designing a tail-recursive function requires you need to create a helper function with additional parameters.

For example, this is not a tail-recursive function:

int factorial(int x) {
    if (x > 0) {
        return x * factorial(x - 1);
    }
    return 1;
}

But this is a tail-recursive function:

int factorial(int x) {
    return tailfactorial(x, 1);
}

int tailfactorial(int x, int multiplier) {
    if (x > 0) {
        return tailfactorial(x - 1, x * multiplier);
    }
    return multiplier;
}

because the compiler could rewrite the recursive function to a non-recursive one, using something like this (a pseudocode):

int tailfactorial(int x, int multiplier) {
    start:
    if (x > 0) {
        multiplier = x * multiplier;
        x--;
        goto start;
    }
    return multiplier;
}

The rule for the compiler is very simple: When you find "return thisfunction(newparameters);", replace it with "parameters = newparameters; goto start;". But this can be done only if the value returned by the recursive call is returned directly.

If all recursive calls in a function can be replaced like this, then it is a tail-recursive function.

Tail-recursion is a form of recursion in which the recursive calls are the last instructions in the function (that's where the tail part comes from). Moreover, the recursive call must not be composed with references to memory cells storing previous values (references other than the parameters of the function). In this way, we don't care about previous values and one stack frame suffices for all of the recursive calls; tail-recursion is one way of optimizing recursive algorithms. The other advantage/optimization is that there is an easy way to transform a tail-recursive algorithm to an equivalent one that uses iteration instead of recursion. So yes, the algorithm for quicksort is indeed tail-recursive.

QUICKSORT(A, p, r)
    if(p < r)
    then
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q–1)
        QUICKSORT(A, q+1, r)

Here is the iterative version:

QUICKSORT(A)
    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        r = q - 1

    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        p = q + 1