I see some times developers do not optimize recursive functions to put less load on stack although many times it can be done with some simple changes in the code without even affecting usability. Lets assume we have a recursive function like the following (which is a C# implementation of the Wikipedia version mentioned here):

public void QuickSort(int[] array, int left, int right) {
If (left < right) {
int pivot = Partition(array, left, right);
QuickSort(array, left, pivot - 1);
QuickSort(array, pivot + 1, right);
}
}

To reduce the call stack depth change the `if`

to `while`

and instead of second recursive call to `QuickSort`

change the `left`

index like this:

public void QuickSort(int[] array, int left, int right) {
while(left < right) {
int pivot = Partition(array, left, right);
QuickSort(array, left, pivot - 1);
left = pivot + 1;
}
}

Some compilers (e.g. F#) detect and optimize these kind of calls in recursive function (tail recursion), but C# is not one of them. IMHO these kind of optimizations are the responsibility of the developer and compiler needs to focus on many different type of optimizations.

Before I forget and just to be complete, here is the the implementation of `Partition`

function:

private int Partition(int[] array, int left, int right, int pivot){
int pivotValue = array[pivot];
// Move pivot to the end of the array
Swap(array, pivot, right);
int sortIndex = left;
for (int i = left; i < right; i++) {
if (array[i] < pivotValue) {
Swap(array, i, sortIndex);
sortIndex++;
}
}
// Move pivot its new place
Swap(array, sortIndex, right);
return sortIndex;
}

### Like this:

Like Loading...

*Related*