CODEWITHSUNDEEP
c#recursion
Kelly Kolesky
Kelly Kolesky

Reputation: 35

Recursion using a for loop for selection sort

I have a recursive selection sort method with an initial recursive call in another method. But I used a for loop in the recursive method. Is it still a recursive method if I have a for loop? How do I implement the selection sort recursively without the for loop?

private static void SelectionSortRecursive(int[] Array, int n) // sorted in descending order recursively
{
    if (n >= Array.Length - 1)
        return;
    int max = n;
    for (int i = n + 1; i < Array.Length; i++)
    {
        if (Array[i] > Array[max])
            max = i;
    }

    swap(Array, n, max);
    SelectionSortRecursive(Array, n + 1);
}

The sorting algorithm works and sorts correctly.

Upvotes: 2

Views: 250

Answers (3)

akg179
akg179

Reputation: 1559

Your solution is recursive in the sense that for determining the value at each stage, you are doing one call to the method itself. Going one step further, you may try making the for loop logic also recursive in itself.

Something like this:

private static void SelectionSortRecursive(int[] Array, int n) // sorted in descending order recursively
{
    if (n >= Array.Length - 1)
        return;
    int max = n;

    max = Compare(Array, max, n+1);
    swap(Array, n, max);
    SelectionSortRecursive(Array, n + 1);
}

private static int Compare(int[] arr, int max, int i)
{
    if(i == arr.Length)
        return max;

    if (arr[i] > arr[max])
        max = i;
    max = Compare(arr,max,++i);
    return max;
}

Upvotes: 0

Kit
Kit

Reputation: 21719

Leaving your for loop in... still recursive because you already have a recursive call, and adding any amount of non-recursion with recursion still leaves recursion.

Implementing the above without a for loop... it can be done. @Emaro's answer is correct in that it does not have an explicit for loop in the code, but the LINQ he's using is still an implicit finite non-recursive iteration over the array... i.e. a loop.

So if you really don't want a loop you can replace that with recursion.

private static void SelectionSortRecursive(int[] arr, int n)
{
    if (n >= arr.Length - 1)
        return;

    int max = n;
    Max(n + 1);

    swap(arr, n, max);
    SelectionSortRecursive(arr, n + 1);

    void Max(int i)
    {
        if (i == arr.Length)
            return;
        if (arr[i] > arr[max])
            max = i;
        Max(i + 1);
    }
}

It's a weird solution, not one I'd write personally, but nevertheless there you go.

Upvotes: 1

Emaro
Emaro

Reputation: 1497

Use the linq method Max() to select the biggest integer. With Skip() we make sure to skip the already sorted elements when asking for the max value. No loop with this code.

private static void SelectionSortRecursive(int[] Array, int n)
{
    if (n >= Array.Length - 1)
        return;

    var max = System.Array.IndexOf(Array, Array.Skip(n).Max());
    swap(Array, n, max);

    SelectionSortRecursive(Array, n + 1);
}

If the code doesn't work this way, make sure to include using System.Linq; on the top of your file.

Edit
Fix indexOf and skip value.

You need to type System.Array since you local var is also called Array. Local vars should be lower camel case. Sample:

private static void SelectionSortRecursive(int[] array, int n)
{
    if (n >= array.Length - 1)
        return;

    var max = Array.IndexOf(array, array.Skip(n).Max());
    swap(array, n, max);

    SelectionSortRecursive(array, n + 1);
}

Upvotes: 0

Related Questions