На курсах получил задание: реализовать метод поиска максимума в массиве рекурсивно. Изначально попытался рекурсивно "повторить" итеративный вариант, т.е. передавать в метод индекс и обновленный максимум. Задание проверяется юнит тестами (написанные авторами курса). Описанный мною подход работал на всех тестах, кроме одного: перфоманс тест, который проверяет реализацию на время ([Timeout(5_000)]
) на довольно большом массиве (длинной 10_000_000). Переписал метод и теперь код выглядит так:
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, 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;
}
Этот вариант проходит все тесты (в том числе и последний "злополучный"). Видимо этот тест как раз и преследовал цель указать обучающемуся (т.е. мне) на проблемы оптимизации и быстродействия. Впереди ряд задач на рекурсию. Может есть какой-нибудь гайдолайн по оптимизации рекурсивного подхода, в какую сторону смотреть? Заранее спасибо. P.S. Это мой первый вопрос и изначально я его сформулировал не верно. Спасибо сообществу, что указали мне на это и прошу прощения.