Найти максимум одномерного массива c помощью рекурсии

Не знаю, как у автора получилось так, что версия с рекурсией выполняется быстрее, чем классическая версия нахождения максимума. Я решил проверить, насколько быстро выполняются методы:

1. классический линейный поиск максимума (FindMaxClassic)
2. рекурсивный метод, предложенный автором (FindMaximumAuthor)
3. рекурсивный метод, предлагаемый мной (FindMaxRecursive)

Итак, я написал три метода и поместил их в один класс IntArrayHelper:

public static class IntArrayHelper
{
    public static int FindMaxClassic(int[] array)
    {
        if (array == null)
        {
            throw new ArgumentNullException(nameof(array));
        }

        if (!array.Any())
        {
            throw new ArgumentException("Array is empty");
        }

        var max = array[0];
        for (var i = 1; i < array.Length; i++)
        {
            if (array[i] > max)
            {
                max = array[i];
            }
        }

        return max;
    }

    public static int FindMaxRecursive(int[] array)
    {
        if (array == null)
        {
            throw new ArgumentNullException(nameof(array));
        }

        if (!array.Any())
        {
            throw new ArgumentException("Array is empty");
        }

        var max = FindMaxRec(array, 0);
        return max;
    }

    private static int FindMaxRec(int[] array, int from)
    {
        // Дошли до крайнего правого элемента массива? заканчиваем рекурсию
        if (from == array.Length - 1)
        {
            return array[from];
        }

        var current = array[from];
        var max = FindMaxRec(array, from + 1);
        return max > current ? max : current;
    }

    public static int FindMaximumAuthor(int[] array)
    {
        if (array is null)
        {
            throw new ArgumentNullException($"source cannot be null.");
        }

        if (array.Length == 0)
        {
            throw new ArgumentException($"source cannot be empty.");
        }

        return FindMax(array, 0, array.Length);
    }

    private static int FindMax(int[] array, int start, int length)
    {
        if (start == length - 1)
        {
            return array[start];
        }

        int mid = (start + length) / 2;
        int left = FindMax(array, start, mid);
        int right = FindMax(array, mid, length);

        return (left > right) ? left : right;
    }
}

И сделал тест на 10000 запусков каждого метода на одинаковом наборе случайно сгенерированного списка массивов. Тестирующий код:

private static void Main(string[] args)
{
    WarmUp();

    var random = new Random();
    var testSrc = new List<int[]>();
    const int n = 10000;
    for (var i = 0; i < n; i++)
    {
        var arrayLength = random.Next(1, n);
        var array = new int[arrayLength];
        for (var j = 0; j < arrayLength; j++)
        {
            array[j] = random.Next(-n, n);
        }

        testSrc.Add(array);
    }

    var timeClassic = TestTimeExecution(IntArrayHelper.FindMaxClassic, testSrc);
    var timeRecursive = TestTimeExecution(IntArrayHelper.FindMaxRecursive, testSrc);
    var timeAuthor = TestTimeExecution(IntArrayHelper.FindMaximumAuthor, testSrc);

    Console.WriteLine($"Classic         : {timeClassic.TotalMilliseconds}");
    Console.WriteLine($"Recursive       : {timeRecursive.TotalMilliseconds}");
    Console.WriteLine($"Author recursive: {timeAuthor.TotalMilliseconds}");
}

private static void WarmUp()
{
    var warmUpTime = TimeSpan.FromSeconds(4);

    var watch = new Stopwatch();
    watch.Start();

    while (watch.Elapsed < warmUpTime)
    {
        var x = Math.Pow(12, 5) * Math.Cos(55.2);
        x /= 20;
    }
}

private static TimeSpan TestTimeExecution(Func<int[], int> method, List<int[]> testSrc)
{
    var watch = new Stopwatch();
    watch.Start();

    foreach (var input in testSrc)
    {
        method(input);
    }

    watch.Stop();
    return watch.Elapsed;
}

Результаты:

Classic : 112,5684

Recursive : 769,2986

Author recursive: 1475,7236

Выводы: Классический метод >10 раз быстрее предложенного вами рекурсивного метода поиска максимума и ~6-7 раз быстрее предложенного мною рекурсивного метода.

P.S. В измерении скорости выполнения методов не силен. Результаты имеют приближенный характер

Оригинальный вариант у вас падал не по таймауту, а по переполнению стека с StackOverflowException.

И тест проверяет не производительность, а ваше понимание потенициальных проблем при использовании рекурсии.

Каждый рекурсивный вызов занимает место в стеке под локальные переменные и под переданные ему параметры. Так что каждый вызов стоит примерно 12 байт в стеке. При линейном рекурсивном вызове на массиве стек выглядит примерно так

FindMax(array, 10000000, ..)
FindMax(array, 9999999, ..)
.....
FindMax(array, 1, ..)
FindMax(array, 0, ..)
FindMaximum(array)

Размер стека фиксированный, порядка мегабайт, и на 10000000 вызовах он просто переполняется.

Разделение массива на резко уменьшило глубину рекурсии, с 10M до примерно 24.

Вместо разделения массива можно использовать оптимизацию Tail Call. Если ваш рекурсивный возвращает в качестве результата или значение, или результат вызова себя, и не делает кроме этого вызова в return других рекурсивных вызовов, то при рекурсивном вызове компилятор может выбросить стек текущего вызова.

Например:

private static int FindMax(int[] array, int index, int currentMax = 0)
{
    if (index == 0)
    {
        currentMax = array[0];
    }
    
    if (index == array.Length)
    {
        return currentMax;
    }
    else
    {
        currentMax = Math.Max(currentMax, array[index]);
        return FindMax(array, index + 1, currentMax);
    }
}

Вызов в стеке

FindMax(array, 0, ..)
FindMaximum(array)

заменится на вызов

FindMax(array, 1, ..)
FindMaximum(array)

и дальше, вплоть до

FindMax(array, 10000000, ..)
FindMaximum(array)

и результат вернется прямо в FindMaximum.

Отрабатывает за 28ms на 10000000 на моей машине :)

Проблема только в том, что компилятор C# не умеет явно требовать этой оптимизации от JIT (компилятор F#, например, умеет). И она срабатывает только в Release, и только в 64 bit (т.е. нужно или собирать или с явным указанием x64, или в AnyCPU со снятой Prefer 32 bit в свойствах проекта).

Если ваше тестовое окружение запускается под x86 (32 bit) - то оптимизация работать не будет, и тест будет падать. Тогда оставляйте вариант с разделением массива.

Полный код, для простоты проверки:

private static int FindMax(int[] array, int index, int currentMax = 0)
{
    if (index == 0)
    {
        currentMax = array[0];
    }
        
    if (index == array.Length)
    {
        return currentMax;
    }
    else
    {
        currentMax = Math.Max(currentMax, array[index]);
        return FindMax(array, index + 1, currentMax);
    }
}

public static int FindMaximum(int[] array)
{
    if (array is null)
    {
        throw new ArgumentNullException($"source cannot be null.");
    }

    if (array.Length == 0)
    {
        throw new ArgumentException($"source cannot be empty.");
    }

    return FindMax(array, 0);
}


static void Main(string[] args)
{
    int[] array = new int[10000000];
    array[array.Length - 50] = 42;

    var sw = Stopwatch.StartNew();
    Console.WriteLine(FindMaximum(array));
    Console.WriteLine(sw.ElapsedMilliseconds);
}