Рекурсивный метод для поиска наибольшего элемента массива?

Question

[piffo]

Задача: написать рекурсивный метод для поиска наибольшего элемента массива.
Реализация в книге:

private static int Max(IEnumerable<int> list)
        {
            if (!list.Any()) throw new ArgumentException(nameof(list));
            if (list.Count() == 1) return list.First();
            if (list.Count() == 2) return list.First() > list.Skip(1).Take(1).First() ? list.First() : list.Skip(1).Take(1).First();
            var sub_max = Max(list.Skip(1));
            return list.First() > sub_max ? list.First() : sub_max;
        }

Мой вариант:

static int Max(IEnumerable<int> list)
        {
            if(list.Count() == 0)
                return 0;
            else
            {
                int subMax = count(list.Skip(1));
                if(list.ToArray()[0] > subMax)
                    return list.ToArray()[0];
                else
                    return subMax;
            }
        }

Какая реализация лучше?

Comments

[Василий Банников]

В твоём варианте не видно рекурсии.
Строка int subMax = count(list.Skip(1)); выглядит подозрительно

[Bazyn]

Понимаю, что пример учебный. Но не забывайте про опасности рекурсии когда работаете со списком не известной длинны, стек не бесконечный.
Max(new int[10000]); // Stack overflow

[#]

поиск наибольшего элемента делается за один проход. изучать на такой задаче рекурсию очень плохой метод. смените книгу

[piffo]

#, грокаем алгоритмы настолько плоха?

[#]

piffo, не читал. так то вроде хвалят. но применять рекурсию для поиска максимального элемента это издевательство над использованием ресурсов. крайне плохой пример, что заставляет задуматься о репутации книги.

Answer 1

[NameOf Var]

По вашей реализации:
1) Конструкцию типа list.Count() == 0 можно заменить спокойно вызовом list.Any()
2) Почему возвращается 0, когда в коллекции нету элементов? Разве это не исключительная ситуация? Может стоит бросать ошибку?
3) Правильно ли я понимаю, что в этой строчке опечатка: int subMax = count(list.Skip(1));. Предполагаю, что вместо вызова метода count() должен вызываться метод Max()?
4) Ваш алгоритм неправильно отработает для случая, когда коллекция содержит только один элемент.
5) Постоянные вызовы list.ToArray() создают лишние объекты в памяти, используйте просто list.ElementAt(index) для получения нужного элемента в коллекции с указанным индексом.

По поводу реализации из книги: в целом, большой разницы между вашей реализации и реализацией из книги я не вижу, т.к. они используют один и тот же принцип рекурсивности. По факту, вы просто заменили тернарный оператор на if и зачем-то убрали остальные проверки. В этом плане алгоритм из книги лучше, т.к. он, во-первых он выбрасывает исключение для пустой коллекции, а во-вторых он правильно отрабатывает для коллекции, состоящей только из одного или двух элементов. Единственное только что меня смущает, так это постоянные вызовы First(), Skip(), Take(). Как по мне, было бы лучше загнать результаты вызовов этих методов единожды в одну переменную и работать уже непосредственно с этой переменной

Answer 2

[Владислав]

Что за книга такая чудесная, которая учит писать код в одну строчку(я про конструкцию if)?
Сейчас повнимательнее глянул, что в одном случае реализация такая себе, что и во втором случае.
Хотя в первом случае рекурсия есть и проглядываются нотки логики, но моменты типа: list.Skip(1).Take(1).First() - это такой бред. Там же понятно, что перечисление из двух элементов. Зачем делать какое-то Skip(), Take(), если можно просто сделать Last()
А насчет изучение алгоритмов - есть более хорошие книги, хоть и не на русском

Comments

[piffo]

Что за книга такая чудесная, которая учит писать код в одну строчку(я про конструкцию if)?

Грокаем алгоритмы. Книга не про кодинг, исходный код был написан автором на Python, может у них там это норма, не знаю.