Лучший способ выучить рекурсивные утверждения и понять их?

Question

Мне трудно читать и понимать рекурсивные утверждения в java.

, если мой профессор показывает нам код и спрашивает, что это делает? что он возвращает? ... Я обнаруживаю, что смотрю на код, как будто он в конечном итоге будет иметь смысл ... но он НИКОГДА не делает.

примеры, такие как ---

public static Int mystery(int[][] a, int b) {
        int x = 0;
        for (int i = 0; i < a.length; i++){
           for (int j = 0; j < a.length; i++){
             x += (a([i][j] == b) ? 1 : 0;
        }

   }
  return x:
}

что возвращает mystery (a, 8), где a = {{6, 4, 5, 8}, {4, 6, 4, 8,}, {7, 3, 6, 4,}, {1, 5 , 7, 8}}

Может кто-нибудь объяснить, пожалуйста? спасибо!

Answer 1

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

Хотя это легче сказать, чем сделать. Как ты это разделил? Вот два подхода: вам понадобятся оба.

Низкий уровень

Один из способов - dry запустить код, инструкцию за инструкцией, как если бы вы были компьютером. Это медленно и утомительно, но дает вам лучшее представление о том, что на самом деле делает компьютер.

Возьмите лист бумаги или виртуальный эквивалент, такой как электронная таблица. Создайте столбец для каждой переменной в методе: a, b, x, i, j. (Сделайте один для очень широкого.)

Метод начинается с установки параметров, поэтому записывайте массив под a и 8 под b. Далее, x установлен в 0, поэтому запишите это под x. Тогда я установлен в 0, и по сравнению с длиной. Массив a имеет четыре элемента, внутренние массивы, поэтому длина равна 4, а текущее значение i, 0 меньше этого значения, поэтому условие выполняется, и мы входим в тело внешнего l oop.

Тело внешнего l oop содержит только внутреннее l oop, которое устанавливает j в 0 и сравнивает его с a.length. Это меньше, поэтому введите тело внутреннего l oop.

Внутреннее тело l oop выполняет несколько операций, начиная справа от =, сначала выясняя, что означает [i]. В настоящее время я равен 0, так что это [0], который является первым подмассивом. Затем вычислите a [0] [j], то есть a [0] [0], что равно 6. Это не равно b, поэтому условие ложно: возьмите 0 и добавьте его к числу под x, 0, и запишите результат под x, чтобы заменить текущее значение. (Замена 0 на 0? Да, это на самом деле ничего не меняет.)

Теперь, когда вы завершили эту итерацию внутреннего тела l oop, выполните i ++ (который, вероятно, должен быть j ++) заменив i на 0 на 1. Затем снова выполните тест: j по-прежнему меньше 4, поэтому снова выполните внутреннее тело l oop, на этот раз с [1] [0].

I ' Я остановлюсь здесь, потому что это действительно утомительно, но, надеюсь, вы сможете увидеть процесс. Внутренний l oop продолжается до тех пор, пока его условие не станет ложным, затем внешний l oop увеличивает i, снова начиная внутренний l oop, но на этот раз, глядя на a [1] [0], a [1] [1 ], и так далее. Это продолжается до тех пор, пока внешний l oop также не выполнит свое условие. Наконец, возвращается последнее значение x, и если вы go выполните все шаги, вы получите тот же результат, что и компьютер. (Попробуйте: как только вы это освоите, это будет быстрее, чем чтение вышеизложенного, слава богу.)

Хорошо, так что это дает вам ту же последовательность шагов, которые выполняет компьютер, и иногда этот уровень детализации неоценим, особенно если у вас есть ошибка, такая как присвоение неправильного имени переменной. Но вы все равно можете не знать , почему эти конкретные операции, не видеть древесину для деревьев. Как вы можете понять, для чего предназначен алгоритм?

Высокий уровень

Другой способ, которым мы можем взглянуть на метод, - это выяснить, что делает каждое утверждение, и каков возможный совокупный эффект может быть. Например, внешний l oop проходит через каждый из вложенных массивов, а внутренний l oop проходит через каждое число во вложенном массиве: поэтому в комбинации они проходят через все числа в массиве a. Итак, что-то происходит со всеми числами.

Кроме того, x устанавливается в 0 в начале, и внутри циклов иногда добавляется 0, а иногда 1. Это говорит нам, что это счетчик, и к концу это скажет нам, как часто условие выполнялось: то есть, сколько чисел в a равно b. И вот что возвращает метод: сколько раз b появляется в a.

Мы также можем указать минимальное возвращаемое значение (0, если ни одно из чисел не совпадает) и максимальное (общее количество чисел). потому что для каждого из них добавляется не более 1).

Это гораздо полезнее: мы знаем, для чего этот метод может быть использован, и мы можем определить худшие случаи: если мы дадим ему более четырех миллиардов чисел, 32-битное int для результата не будет ' например, этого будет недостаточно; но он не будет работать вечно (при условии j ++), потому что массив имеет фиксированный размер, и он не исчерпает память, потому что он не выделяет ничего, кроме переменных.

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

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

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

Answer 2

Привет, добро пожаловать в мир программирования. Это не рекурсивное программирование. Рекурсивный - это когда функция вызывает себя. Например, удалите files () ->, который будет вызывать себя снова, когда есть папка, и вы хотите снова и снова удалять файлы в ней.

Ваш пример называется 'Nested Loops' -> Loops of Циклы, и условие «a.length», используемое в i и j, неверно.

Вы пытаетесь получить l oop массивов массивов, трехмерную таблицу. Это должно быть что-то вроде этого.

int x = 0;
for (int i = 0; i < a.length; ++i){
    for (int j = 0; j < a[i].length; ++j){
        if (a[i][j] == b) {
            ++x;
        }
}
return x;

Изменения:

1. Старайтесь не использовать «троичный оператор» ?:, так как это может сбить вас с толку как начинающего.
2. максимальная длина внутреннего l oop должна быть длиной [i]
3. при использовании ++ i лучше, чем i ++, если вы не используете значение напрямую.

Представьте себе [[1,1,1], [2,2]] в вашем первом l oop, длина [0]. Будет 3. в вашем втором l oop, длина [1]. Будет 2.

как for ++ i против i ++:

++i is modifying i directly, making the value +1 instantly
i++ means var b = i; i = b + 1;

создает новую временную переменную для хранения исходного значения i. пример:

int i = 0, j = 0;
System.out.println(i++); // will print 0, but i will be 1 moving forward
System.out.println(++j); // will print 1, and j will be 1 moving forward

вы узнаете больше об этом в будущем.