C# sort List recursively

Question

there's an exercise i need to do, given a List i need to sort the content using ONLY recursive methods (no while, do while, for, foreach).

So... i'm struggling (for over 2 hours now) and i dont know how to even begin. The function must be

List<int> SortHighestToLowest (List<int> list) {

}

I THINK i should check if the previous number is greater than the actual number and so on but what if the last number is greater than the first number on the list?, that's why im having a headache.

I appreciate your help, thanks a lot.

[EDIT]

I delivered the exercise but then teacher said i shouldn't use external variables like i did here:

    List<int> _tempList2 = new List<int>();
    int _actualListIndex = 0;
    int _actualMaxNumber = 0;
    int _actualMaxNumberIndex = 0;

    List<int> SortHighestToLowest(List<int> list)
    {
        if (list.Count == 0)
            return _tempList2;

        if (_actualListIndex == 0)
            _actualMaxNumber = list[0];

        
        if (_actualListIndex < list.Count -1)
        {
            _actualListIndex++;

            if (list[_actualListIndex] > _actualMaxNumber)
            {
                _actualMaxNumberIndex = _actualListIndex;
                _actualMaxNumber = list[_actualListIndex];
            }

            return SortHighestToLowest(list);
        }

        _tempList2.Add(_actualMaxNumber);
        list.RemoveAt(_actualMaxNumberIndex);
        _actualListIndex = 0;
        _actualMaxNumberIndex = 0;
        return SortHighestToLowest(list);
    }

Exercise is done and i approved (thanks to other exercises as well) but i was wondering if there's a way of doing this without external variables and without using System.Linq like String.Empty's response (im just curious, the community helped me to solve my issue and im thankful).

Does this answer your question? [Bubble sort using recursion in C#](https://stackoverflow.com/questions/1644440/bubble-sort-using-recursion-in-c-sharp) — devNull, Nov 25 '20 at 22:22
@devNull no but its a start, i'll use that as a "template". Thanks! — DEFALTUSER, Nov 25 '20 at 22:32
You may want to do it for `List where T:IComparable`. It will be the same logic (except you will use `IComparable` methods instead of something like `<` or `>`). Since integers are comparable, they will *just work* — Flydog57, Nov 25 '20 at 23:07
People requesting closure due to perceived _"focus"_ should perhaps take note of _[Is it always a good idea to demand the OP “post some code”?](https://meta.stackoverflow.com/a/286760/585968)_ — , Nov 26 '20 at 00:46

score 0 · Answer 1 · answered Nov 25 '20 at 23:49

For solving this problem, try to solve smaller subsets. Consider the following list

[1,5,3,2]

Let's take the last element out of list, and consider the rest as sorted which will be [1,3,5] and 2. Now the problem reduces to another problem of inserting this 2 in its correct position. If we can insert it in correct position then the array becomes sorted. This can be applied recursively.
For every recursive problem there should be a base condition w.r.t the hypothesis we make. For the first problem the base condition is array with single element. A single element array is always sorted.
For the second insert problem the base condition will be an empty array or the last element in array is less than the element to be inserted. In both cases the element is inserted at the end.

Algorithm
---------
Sort(list)
   if(list.count==1)
       return
   temp = last element of list
   temp_list = list with last element removed
   Sort(temp_list)
   Insert(temp_list, temp)

Insert(list, temp)
   if(list.count ==0 || list[n-1] <= temp)
      list.insert(temp)
      return
   insert_temp = last element of list
   insert_temp_list = list with last element removed

   Insert(insert_temo_list, insert_temp)

For Insert after base condition its calling recursively till it find the correct position for the last element which is removed.

Your code helped me with logic, i just edited my answer to show what i've done in case you're curious. Thanks! — DEFALTUSER, Nov 26 '20 at 19:14

score 0 · Accepted Answer · answered Nov 26 '20 at 04:01

I am taking your instructions to the letter here.

Only recursive methods
No while, do while, for, foreach
Signature must be List<int> SortHighestToLowest(List<int> list)

Now, I do assume you may use at least the built-in properties and methods of the List<T> type. If not, you would have a hard time even reading the elements of your list.

That said, any calls to Sort or OrderBy methods would be beyond the point here, since they would render any recursive method useless.

I also assume it is okay to use other lists in the process, since you didn't mention anything in regards to that.

With all that in mind, I came to this piece below, making use of Max and Remove methods from List<T> class, and a new list of integers for each recursive call:

    public static List<int> SortHighestToLowest(List<int> list)
    {
        // recursivity breaker
        if (list.Count <= 1)
            return list;

        // remove highest item
        var max = list.Max();
        list.Remove(max);

        // append highest item to recursive call for the remainder of the list
        return new List<int>(SortHighestToLowest(list)) { max };
    }

This is exactly what i was looking for, now i have a question, is there a way of doing this **without** using list.Max()? (just curious). Oh and just so u know, i edited the answer with the code i used to approve. — DEFALTUSER, Nov 26 '20 at 19:11
@DEFALTUSER Hey there. Glad to help. I checked your edit, well done! Yes, I understand some people may frown upon the usage of Max(). I do too, actually, ehehe. But given the other constraints, it would be very hard to achieve that without Max() or Min(). Most codes out there have some flexibility on using loops and having other variables passed in as parameters to the recursive method, but this exercise explicitly forbids those. That said, I will give it another try and update this answer if I get anywhere. Cheers! — String.Empty, Nov 26 '20 at 21:15

C# sort List recursively

2 Answers2