Changing my iterative selection sort into a recursive sort using C#

Question

I've tried changing my sort into a recursive function where the method calls itself. At least that's my understanding of recursion to forego for loops and the method calls itself to repeat the necessary iterations.

Below is my iterative verion:

for (int i = 0; i < Integers.Count; i++) //loops through all the numbers
{
    min = i; //setting the current index number to be the minimum

    for (int index = i + 1; index < Integers.Count; index++) //finds and checks pos of min value 
    {                                                        //and switches it with last element using the swap method
        if ((int) Integers[index] > (int) Integers[min]) {
            min = index;
        }
        comparisons++;
    }
    if (i != min) //if statement for if swop is done
    {
        Swap(i, min, Integers, ref swops); //swap method called
    }
    //Swap method called
}

I've tried making it recursive. I read online that it was OK to still have for loops in a recursive funtion which I guess is not true. I just havent been able to develop a working sort. Am I going to need to split the method into 2 where one method traverses a list and the other does the sort?

Here's my selection sort recursive method attempt below:

static void DoSelectionSortRecursive(ArrayList Integers, int i, int swops, int comparisons) {

    int min;
    min = i;
    for (int index = i + 1; index < Integers.Count; index++) //read online that the use of arraylists are deprecated, and i shoudlve rather used List<int> in order to remedy the code. is it necassary 
    {

        if ((int) Integers[index] > (int) Integers[min]) {
            min = index;
        }
        comparisons++;
    }
    if (i != min) {
        Swap(i, min, Integers, ref swops);
    }
    DoSelectionSortRecursive(Integers, (i + 1), comparisons, swops); //DoSelectionSortRecursive method called 
}

This is my imporved attempt including performance measures and everything. The original list of integers in the unsorted lists. 84,24,13,10,37.
and im getting 84,24,13,37,10. clearly not in a sorted descending order. below is the improved code

static void DoSelectionSortRecursive(ArrayList Integers)
    {

        Stopwatch timer = new Stopwatch();
        timer.Start();
        int shifts = 0;
        int swops = 0;
        int comparisons = 0;

        Sort(Integers, 1,ref swops,ref comparisons);   

        timer.Stop();
        Console.WriteLine("Selection Sort Recursive: ");
        Console.WriteLine(timer.ElapsedMilliseconds);
        Console.WriteLine(swops);
        Console.WriteLine(comparisons);
        Console.WriteLine(shifts);      //not needed in this sort
        Console.WriteLine("-------------------------------------");
        foreach (int i in Integers)
        {
            Console.WriteLine(i);
        }

    }

    static void Sort(ArrayList Integers, int i, ref int swops, ref int comparisons)
    {
        int min = i;
        int index = i + 1;
        if (index < Integers.Count)        //read online that the use of arraylists are deprecated, and i shoudlve rather used List<int> in order to remedy the code. is it necassary 
        {

            if ((int)Integers[index] > (int)Integers[min])
            {
                min = index;
            }
            comparisons++;
            index++;
        }
        if (i != min)
        {
            Swap(i, min, Integers, ref swops);
        }
        if (i < Integers.Count - 1)
        {
            Sort(Integers, (i + 1), ref comparisons, ref swops);     //DoSelectionSortRecursive method called 
        }

    }

 static void Swap(int x, int y, ArrayList Integers, ref int swap)      //swap method, swaps the position of 2 elements
    {
        swap++;
        int temporary = (int)Integers[x];                   //essentially will swap the min with the current position
        Integers[x] = Integers[y];
        Integers[y] = temporary;
    }

Answer 1

There are no "rules" about recursion that say you cannot use loops in the recursive method body. The only rule in recursion is that the function has to call itself, which your second code snippet does, so DoSelectionSortRecursive is legitimately recursive.

For example, merge sort uses recursion for splitting the array and loops for merging the sorted subarrays. It'd be wrong to call it anything but a recursive function, and it'd be somewhat silly to implement the merging stage (an implementation detail of merge sort) recursively -- it'd be slower and harder to reason about, so loops are the natural choice.

On the other hand, the splitting part of merge sort makes sense to write recursively because it chops the problem space down by a logarithmic factor and has multiple branches. The repeated halving means it won't need to make more than a few or a dozen recursive calls on a typical array. These calls don't incur much overhead and fit well within the call stack.

On the other hand, the call stack can easily blow for linear recursive algorithms in languages without tail-call optimization like C# where each index in the linear structure requires a whole stack frame.

Rules prohibiting loops are concoted by educators who are trying to teach recursion by forcing you to use a specific approach in your solution. It's up to your instructor to determine whether one or both loops need to be converted to recursion for it to "count" as far as the course is concerned. (apologies if my assumptions about your educational arrangement are incorrect)

All that is to say that this requirement to write a nested-loop sort recursively is basically a misapplication of recursion for pedagogical purposes. In the "real world", you'd just write it iteratively and be done with it, as Google does in the V8 JavaScript engine, which uses insertion sort on small arrays. I suspect there are many other cases, but this is the one I'm most readily familiar with.

The point with using simple, nested loop sorts in performance-sensitive production code is that they're not recursive. These sorts' advantage is that they avoid allocating stack frames and incurring function call overhead to sort small arrays of a dozen numbers where the quadratic time complexity isn't a significant factor. When the array is mostly sorted, insertion sort in particular doesn't have to do much work and is mostly a linear walk over the array (sometimes a drawback in certain real-time applications that need predictable performance, in which case selection sort might be preferable -- see Wikipedia).

---

Regarding ArrayLists, the docs say: "We don't recommend that you use the ArrayList class for new development. Instead, we recommend that you use the generic List<T> class." So you can basically forget about ArrayList unless you're doing legacy code (Note: Java does use ArrayLists which are more akin to the C# List. std::list isn't an array in C++, so it can be confusing to keep all of this straight).

---

It's commendable that you've written your sort iteratively first, then translated to recursion on the outer loop only. It's good to start with what you know and get something working, then gradually transform it to meet the new requirements.

Zooming out a bit, we can isolate the role this inner loop plays when we pull it out as a function, then write and test it independent of the selection sort we hope to use it in. After the subroutine works on its own, then selection sort can use it as a black box and the overall design is verifiable and modular.

More specifically, the role of this inner loop is to find the minimum value beginning at an index: int IndexOfMin(List<int> lst, int i = 0). The contract is that it'll throw an ArgumentOutOfRangeException error if the precondition 0 <= i < lst.Count is violated.

I skipped the metrics variables for simplicity but added a random test harness that gives a pretty reasonable validation against the built-in sort.

using System;
using System.Collections.Generic;
using System.Linq;

class Sorter
{
    private static void Swap(List<int> lst, int i, int j)
    {
        int temp = lst[i];
        lst[i] = lst[j];
        lst[j] = temp;
    }

    private static int IndexOfMin(List<int> lst, int i = 0)
    {
        if (i < 0 || i >= lst.Count)
        {
            throw new ArgumentOutOfRangeException();
        }
        else if (i == lst.Count - 1)
        {
            return i;
        }

        int bestIndex = IndexOfMin(lst, i + 1);
        return lst[bestIndex] < lst[i] ? bestIndex : i;
    }
    
    public static void SelectionSort(List<int> lst, int i = 0)
    {
        if (i < lst.Count)
        {
            Swap(lst, i, IndexOfMin(lst, i));
            SelectionSort(lst, i + 1);
        }
    }

    public static void Main(string[] args) 
    {
        var rand = new Random();
        int tests = 1000;
        int lstSize = 100;
        int randMax = 1000;

        for (int i = 0; i < tests; i++)
        {
            var lst = new List<int>();

            for (int j = 0; j < lstSize; j++)
            {
                lst.Add(rand.Next(randMax));
            }

            var actual = new List<int>(lst);
            SelectionSort(actual);
            lst.Sort();

            if (!lst.SequenceEqual(actual))
            {
                Console.WriteLine("FAIL:");
                Console.WriteLine($"Expected => {String.Join(",", lst)}");
                Console.WriteLine($"Actual   => {String.Join(",", actual)}\n");
            }
        }
    }
}

Here's a more generalized solution that uses generics and CompareTo so that you can sort any list of objects that implement the IComparable interface. This functionality is more akin to the built-in sort.

using System;
using System.Collections.Generic;
using System.Linq;

class Sorter
{
    public static void Swap<T>(List<T> lst, int i, int j)
    {
        T temp = lst[i];
        lst[i] = lst[j];
        lst[j] = temp;
    }

    public static int IndexOfMin<T>(List<T> lst, int i = 0)
        where T : IComparable<T>
    {
        if (i < 0 || i >= lst.Count)
        {
            throw new ArgumentOutOfRangeException();
        }
        else if (i == lst.Count - 1)
        {
            return i;
        }

        int bestIndex = IndexOfMin(lst, i + 1);
        return lst[bestIndex].CompareTo(lst[i]) < 0 ? bestIndex : i;
    }
    
    public static void SelectionSort<T>(List<T> lst, int i = 0)
        where T : IComparable<T>
    {
        if (i < lst.Count)
        {
            Swap(lst, i, IndexOfMin(lst, i));
            SelectionSort(lst, i + 1);
        }
    }

    public static void Main(string[] args) 
    {
        // same as above
    }
}

Since you asked how to smush both of the recursive functions into one, it's possible by keeping track of both i and j indices in the parameter list and adding a branch to figure out whether to deal with the inner or outer loop on a frame. For example:

public static void SelectionSort<T>(
    List<T> lst, 
    int i = 0, 
    int j = 0, 
    int minJ = 0
) where T : IComparable<T>
{
    if (i >= lst.Count)
    {
        return;
    }
    else if (j < lst.Count)
    {
        minJ = lst[minJ].CompareTo(lst[j]) < 0 ? minJ : j;
        SelectionSort(lst, i, j + 1, minJ);
    }
    else
    {
        Swap(lst, i, minJ);
        SelectionSort(lst, i + 1, i + 1, i + 1);
    }
}

All of the code shown in this post is not suitable for production -- the point is to illustrate what not to do.