Нахождение самого большого положительного интервала в массиве рекурсией
Я решил реализовать очень простую программу рекурсивно, видеть, как хорошо Java обрабатывает рекурсию* и подошел немного короткий. Это - то, что я закончил тем, что писал:
public class largestInIntArray {
public static void main(String[] args)
{
// These three lines just set up an array of ints:
int[] ints = new int[100];
java.util.Random r = new java.util.Random();
for(int i = 0; i < 100; i++) ints[i] = r.nextInt();
System.out.print("Normal:"+normal(ints,-1)+" Recursive:"+recursive(ints,-1));
}
private static int normal(int[] input, int largest) {
for(int i : input)
if(i > largest) largest = i;
return largest;
}
private static int recursive(int[] ints, int largest) {
if(ints.length == 1)
return ints[0] > largest ? ints[0] : largest;
int[] newints = new int[ints.length - 1];
System.arraycopy(ints, 1, newints, 0, ints.length - 1);
return recursive(newints, ints[0] > largest ? ints[0] : largest);
}
}
И это хорошо работает, но поскольку это немного ужасно, я задался вопросом, был ли лучший путь. Если бы у кого-либо есть какой-либо сахар мыслей/альтернатив/синтаксических для совместного использования, это очень ценилось бы!
P.s. Если Вы говорите, "используют Lisp", Вы ничего не выигрываете (но уважение). Я хочу знать, может ли это быть сделано выглядеть хорошим в Java.
*и как хорошо я обрабатываю рекурсию
7 ответов
2-улучшения:
- нет необходимости делать копию массива (просто используя смещение)
нет необходимости давать текущий max
private static int recursive(int[] ints, int offset) { если (ints.length - 1 == offset) { возвращаемые вставки[смещение]; иначе возвращает Math.max(ints[offset], рекурсивный(ints, offset + 1)); } }
Начните рекурсию с рекурсивного(ints, 0).
Вот как я могу заставить рекурсивный метод выглядеть лучше:
private static int recursive(int[] ints, int largest, int start) {
if (start == ints.length) {
return largest;
}
return recursive(ints, Math.max(ints[start], largest), start + 1);
}
Это позволяет избежать дорогостоящего копирования массива и работает для пустого входного массива. Можно реализовать дополнительный перегруженный метод только с двумя параметрами для той же сигнатуры, что и итерационная функция:
private static int recursive(int[] ints, int largest) {
return recursive(ints, largest, 0);
}
Можно передавать текущий индекс в качестве параметра, а не копировать каждый раз почти весь массив, или можно использовать подход "разделяй и властвуй"
.public static int max(int[] numbers) {
int size = numbers.length;
return max(numbers, size-1, numbers[size-1]);
}
public static int max(int[] numbers, int index, int largest) {
largest = Math.max(largest, numbers[index]);
return index > 0 ? max(numbers, index-1, largest) : largest;
}
... чтобы увидеть, насколько хорошо Java обрабатывает рекурсию
Простой ответ - Java плохо обрабатывает рекурсию. В частности, компиляторы Java Sun и JVM Hotspot не реализуют оптимизацию рекурсии по хвостовому вызову, поэтому алгоритмы, интенсивно использующие рекурсии, могут легко потреблять много стека.
Однако, я видел статьи, в которых говорилось, что JVM от IBM do поддерживают эту оптимизацию. И я видел письмо от какого-то парня не из Солнца, который сказал, что он добавляет его как экспериментальное расширение Hotspot в качестве диссертационного проекта
.Вот небольшая вариация, показывающая, что Связанные списки часто немного лучше для рекурсии, где "лучше" означает "меньше параметров в сигнатуре метода"
private static int recursive(LinkedList<Integer> list) {
if (list.size() == 1){
return list.removeFirst();
}
return Math.max(list.removeFirst(),recursive(list));
}
Ваш рекурсивный код использует System.arrayCopy, но ваш итерационный код этого не делает, так что ваш микробенчмарк не будет точным. Как упоминали другие, вы можете очистить этот код, используя Math.min и используя индекс массива вместо подхода, подобного очереди, который у вас был.