Рефакторинг это рекурсивный метод?

Question

Я довольно новичок в идее рекурсии, и это на самом деле моя первая попытка написать рекурсивный метод.

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

Это работает, но это просто не чувствую правильно!

Я также заметил, что мне кажется, что я использую модификатор static гораздо чаще, чем мои одноклассники ...

Кто-нибудь может дать какие-либо общие советы, а также отзывы о том, как я могу улучшить свой код?

public class RecursiveTry{

static int[] n = new int[] {1,2,4,3,3,32,100};
static int current = 0;
static int maxValue = 0;
static int SIZE = n.length;

public static void main(String[] args){
    System.out.println(Max(n, SIZE));
}   

public static int Max(int[] n, int SIZE) {
    if(current <= SIZE - 1){
        if (maxValue <= n[current]) {
            maxValue = n[current];
            current++;
            Max(n, SIZE);                       
        }
        else {
            current++;
            Max(n, SIZE);
        }
    }
    return maxValue;
}

}

Answer 1

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

Примером рекурсивной реализации функции max () в псевдокоде может быть:

function Max(data, size) {
    assert(size > 0)
    if (size == 1) {
        return data[0]
    }
    maxtail = Max(data[1..size], size-1)
    if (data[0] > maxtail) {
        return data[0]
    } else {
        return maxtail
    }
}

Ключом здесь является рекурсивный вызов Max (), где вы передаете все , кроме первого элемента, и на один размер меньше. Общая идея заключается в том, что эта функция говорит, что «максимальное значение в этих данных является либо первым элементом, либо максимумом значений в остальной части массива, в зависимости от того, что больше».

Эта реализация не требует статических данных вне определения функции.

Одним из отличительных признаков рекурсивных реализаций является так называемое «условие завершения», которое предотвращает вечную рекурсию (или до тех пор, пока вы не получите переполнение стека). В приведенном выше случае проверка для size == 1 является условием завершения.

Answer 2

Делать вашу функцию зависимой от статических переменных не очень хорошая идея. Здесь возможна реализация рекурсивной функции Max:

int Max(int[] array, int currentPos, int maxValue) {
    // Ouch!
    if (currentPos < 0) {
        raise some error
    }
    // We reached the end of the array, return latest maxValue
    if (currentPos >= array.length) {
        return maxValue;
    }
    // Is current value greater then latest maxValue ?
    int currentValue = array[currentPos];
    if (currentValue > maxValue) {
        // currentValue is a new maxValue
        return Max(array, currentPos + 1, currentValue);
    } else {
        // maxValue is still a max value
        return Max(array, currentPos + 1, maxValue);
    }
}
...

int[] array = new int[] {...};
int currentPos = 0;
int maxValue = array[currentPos] or minimum int value;  
    maxValue = Max(array, currentPos, maxValue);

Answer 3

Функция "max" - это неправильный тип вещи, для которого нужно написать рекурсивную функцию - и тот факт, что вы используете статические значения для "current" и "maxValue", делает вашу функцию не совсем рекурсивной функцией. *

Почему бы не сделать что-то более поддающееся рекурсивному алгоритму, например, факториал?

Answer 4

Вот вам версия Java.

public class Recursion {

    public static void main(String[] args) {
        int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        System.out.println("Max: " + max(0, data));
    }

    public static int max(int i, int[] arr) {
        if(i == arr.length-1) {
            return arr[i];
        }

        int memo = max(i+1, arr);
        if(arr[i] > memo) {
            return arr[i];
        }
        return memo;
    }
}

Отношение повторения состоит в том, что максимальный элемент массива является либо первым элементом, либо максимумом остальной части массива. Условие остановки достигается, когда вы достигаете конца массива. Обратите внимание на использование памятки для сокращения рекурсивных вызовов (примерно) вдвое.

Answer 5

Как уже отмечалось, не требуется для рекурсии для реализации функции Max, но может быть полезно использовать знакомый алгоритм для экспериментов с новой концепцией. Итак, вот упрощенный код с пояснениями ниже:

public class RecursiveTry
{
    public static void main(String[] args)
    {
        System.out.println(Max(new int[] {1,2,4,3,3,32,100}, 0, 0));
    }   

    public static int Max(int[] n, int current, int maxValue) 
    {
        if(current < n.Length)
        {
            if (maxValue <= n[current] || current == 0))
            {
                return Max(n, current+1, n[current]);
            }
            return Max(n, current+1, maxValue);
        }
        return maxValue;
   }
}

все статическое состояние ушло за ненадобностью; вместо этого все передается в стеке. внутренняя логика функции Max упорядочена, и мы повторяем два разных способа ради интереса

Answer 6

"не-домашнее задание"?

В любом случае. Обо всем по порядку.

static int[] n = new int[] {1,2,4,3,3,32,100};
static int SIZE = n.length;

не имеет ничего общего с параметрами Max (), с которыми они делятся своими именами. Переместите их в main и потеряйте «статические» спецификаторы. Они используются только один раз, при вызове первого экземпляра Max () из main (). Их область не должна выходить за пределы main ().

Нет никаких причин для всех вызовов Max () использовать один «текущий» индекс. «current» должен быть локальным по отношению к Max (). Но тогда как последовательные повторения Max () узнают, какое значение «current» использовать? (Подсказка: Max () уже передает другим Max () ниже линии некоторые данные. Добавьте «current» к этим данным.)

То же самое относится и к maxValue, хотя ситуация здесь немного сложнее. Вам нужно не только передать текущее значение «maxValue» по линии, но и когда рекурсия завершится, вы должны передать его обратно до первой функции Max (), которая вернет его в main (). Возможно, вам придется взглянуть на некоторые другие примеры рекурсии и потратить некоторое время с этим.

Наконец, сам Max () является статическим. Однако, как только вы избавились от необходимости ссылаться на внешние данные (статические переменные); это на самом деле не имеет значения. Это просто означает, что вы можете вызывать Max () без создания экземпляра объекта.

Answer 7

Наименьший размер кода, который я мог получить:

public class RecursiveTry {
    public static void main(String[] args) {
        int[] x = new int[] {1,2,4,3,3,32,100};
        System.out.println(Max(x, 0));
    }   

    public static int Max(int[] arr, int currPos) {
        if (arr.length == 0) return -1;
        if (currPos == arr.length) return arr[0];
        int len = Max (arr, currPos + 1);
        if (len < arr[currPos]) return arr[currPos];
        return len;
    }
}

Несколько вещей:

1 / Если массив имеет нулевой размер, он возвращает максимум -1 (у вас может быть другое значение маркера, скажем, -MAX_INT или выдается исключение). Я сделал предположение для ясности кода, чтобы предположить, что все значения равны нулю или больше. В противном случае я бы засыпал код всякими ненужными вещами (что касается ответа на вопрос).

2 / Большинство рекурсий, по моему мнению, «чище», если завершающий регистр - это «нет данных», а не «последние данные», поэтому я возвращаю значение, которое гарантированно будет меньше или равно макс. , Другие могут расходиться во мнениях, но это не первый или последний раз, когда они ошибаются: -).

3 / Рекурсивный вызов просто получает максимум остальной части списка и сравнивает его с текущим элементом, возвращая максимум двух.

4 / «Идеальным» решением было бы передать модифицированный массив при каждом рекурсивном вызове, чтобы вы сравнивали только первый элемент с остальным списком, устраняя необходимость в currPos. Но это было бы неэффективно и вызвало бы гнев SO.

5 / Это не обязательно является лучшим решением. Возможно, из-за чрезмерного использования LISP с помощью CAR, CDR и этих бесконечных скобок может быть скомпрометировано серое вещество.

Answer 8

Лучшим способом рекурсивного получения максимального значения массива было бы реализовать быстрая сортировка (это хороший, рекурсивный алгоритм сортировки), а затем просто вернуть первое значение.

Вот немного Java-кода для быстрой сортировки .

Answer 9

На схеме это можно записать очень кратко:

(define (max l)
    (if (= (length l) 1)
        (first l)
        (local ([define maxRest (max (rest l))])
          (if (> (first l) maxRest)
              (first l)
              maxRest))))

Конечно, здесь используются связанные списки, а не массивы, поэтому я не передал ему элемент размера, но я чувствую, что это сводит проблему к ее сути. Это определение псевдокода:

define max of a list as:
    if the list has one element, return that element
    otherwise, the max of the list will be the max between the first element and the max of the rest of the list

Answer 10

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

static int [] n = new int [] {1,2,4,3,3,32,100}; статический int current = 0; static int maxValue = 0; static int SIZE = n.length;

в вашу функцию main (), чтобы они были локальными переменными.

public static void main(String[] args)
{
  int[] n = new int[] {1,2,4,3,3,32,100};
  int current = 0;
  int maxValue = 0;
  int SIZE = n.length;
  ...other code

}

Не решение вашего основного вопроса, но рекомендуется использовать локальные переменные над глобальными (в общем)

--- Когда я заканчиваю это, я понимаю, что просто активирую то, что сказано выше.