cannot return maximum element

Question

I am trying to return maximum element from array using recursion
here is my code

    static void Main(string[] args)
    {
        int[] Array=new int[]{10,233,34};

        int _MaxVal = CalculateMax(Array, 0, 0);
        Console.WriteLine(_MaxVal);
        Console.ReadKey();

    }

    private static int CalculateMax(int[] Array, int Startpos, int maxval)
    {
        if (Startpos != Array.Length)
        {
            if (Array[Startpos] > maxval)
            {
                maxval = Array[Startpos];
            }


            CalculateMax(Array, ++Startpos, maxval);
        }

        return maxval;
    }

I am getting MaxVal as 10 .

What is wrong with it ??

Thanks all

Do you also want to do `maxval = CalculateMax(Array, ++Startpos, maxval);`? — Jonny, Jan 16 '14 at 14:29
You're not taking into account the return value of `CalculateMax()` when you call it recursively. — Frédéric Hamidi, Jan 16 '14 at 14:29
Learning recursion is good, but not everything needs to be (or should be) recursive. — crashmstr, Jan 16 '14 at 14:31

score 7 · Answer 1 · answered Jan 16 '14 at 14:30

7

You're losing the value of maxval.

Try this:

maxval = CalculateMax(Array, ++Startpos, maxval);

Unless you're doing this as a personal exercise or for an assignment, you could handle this way more gracefully with LINQ:

var maxValue = Array.Max();

answered Jan 16 '14 at 14:30

Grant Winney

65,241
13
115
165

1

+1. I'd also add that it would be better to have an initial value for `maxval` of `int.MinValue`, as otherwise if the maximum value is less than zero, the result is wrong. (Just what should be done if the array is empty is another question). – Jon Hanna Jan 16 '14 at 14:37

kokluch · Answer 2 · 2014-01-16T16:05:04.873

To use recursion you should have a stop test and be sure to always launch the next step on a smaller problem.

Try this : (Not sure if Array.SubArray(int) is a real function but that is the idea.

static void Main(string[] args)
{
    int[] Array=new int[]{10,233,34};

    int _MaxVal = CalculateMax(Array);
    Console.WriteLine(_MaxVal);
    Console.ReadKey();

}

private static int CalculateMax(int[] Array)
{
    if (Array.Length > 0)
    {
        int maxSubArray = CalculateMax(Array.SubArray(1)); // Use recursive function on the SubArray starting at index 1 (that the smaller problem)
        if (maxSubArray > Array[0])
        {
            return maxSubArray;
        } else {
            return Array[0];
        }

    } else {
        return 0; // Stop test
    }
}

Note : it will not work with negative value.

score 0 · Answer 3 · answered Jan 16 '14 at 14:33

    static void Main(string[] args)
    {
        int[] Array = new int[] { 10, 233, 34 };

        int _MaxVal = CalculateMax(Array);
        Console.WriteLine(_MaxVal);
        Console.ReadKey();

    }
    private static int CalculateMax(int[] Array)
    {
        int max = 0;
        for (int i = 0; i < Array.Length; i++)
            if (Array[i] > max)
                max = Array[i];
        return max;
    }

OR

var max1 = Array.Max();
var max2 = Array.Concat(new[] { 0 }).Max();
var max3 = Array.OrderByDescending(p => p).FirstOrDefault();

score 0 · Answer 4 · answered Jan 16 '14 at 15:09

You don't use return value from deeper calls of CalculateMax

Change

CalculateMax(Array, ++Startpos, maxval);

to

maxval = CalculateMax(Array, ++Startpos, maxval);

This way you pass maxval not only forward, but also backwards to main().

As (probably) said before, recursion is not best way to do it, because stack overflow may happen.

score -1 · Answer 5 · answered Jan 16 '14 at 14:38

You are not using the return value from the recursive call. This:

CalculateMax(Array, ++Startpos, maxval);

should be:

maxval = CalculateMax(Array, ++Startpos, maxval);

Anyway, you are using recursion instead of a loop, which is a very bad way to use recursion. You will be doing recursion as deep as there are items in the array, which means that you have a very slow loop, and you will get a stack overflow if the array is too large.

To use recursion correctly you should divide the work into smaller parts, and use recursion to handle those smaller parts, until the parts are so small that they are trivial.

For example, split the array in half for each level:

int[] Array = new int[]{ 10, 233, 34 };
int _MaxVal = CalculateMax(Array, 0, Array.Length);
Console.WriteLine(_MaxVal);

private static int CalculateMax(int[] array, int start, int length) {
  if (length == 1) {
    return array[start];
  } else {
    int half = length / 2;
    int first = CalculateMax(array, start, half);
    int second = CalculateMax(array, start + half, length - half);
    return first > second ? first : second;
  }
}

This is not a bad way to use recursion, using recursion at then end of a function can be optimized to a loop and is a common pattern http://en.wikipedia.org/wiki/Tail_call — Hogan, Jan 16 '14 at 19:39
@Hogan: C# doesn't do tail recursion: http://stackoverflow.com/questions/491376/why-doesnt-net-c-optimize-for-tail-call-recursion — Guffa, Jan 16 '14 at 21:39
Slightly out of date - http://blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/tail-call-improvements-in-net-framework-4.aspx — Hogan, Jan 16 '14 at 21:41
@Hogan: Thanks for the update. Note though that it only does this in x64 mode, not x86 mode. Anyhow, the code in the question doesn't do tail recursion in any case, so it's still a bad use of recusion. — Guffa, Jan 16 '14 at 22:03

cannot return maximum element

5 Answers5