$5.$ Problem $7-4($page $188)$ on Tail$-$Recursive$-$Quicksort$\mathrm{.}7-4$ Stack depth for quicksort

The QUICKSORT algorithm of Section $7\mathrm{.}1$ contains two recursive calls to itself.

After QUICKSORT calls PARTITION, it recursively sorts the left subarray and then

it recursively sorts the right subarray. The second recursive call in QUICKSORT

is not really necessary; we can avoid it by using an iterative control structure.

This technique, called tail recursion, is provided automatically by good compilers.

Consider the following version of quicksort, which simulates tail recursion:

TAIL$-$RECURSIVE$-$QUICKSORT $(A,p,r)$

while $q=$PARTITION$(A,p,r)(A,p,q-1)p=q+1A,1$