Рекурсивный обход массива java

Рекурсия

Язык Java поддерживает рекурсию. Рекурсия в программировании — это когда метод вызывает сам себя. В таком случае метод называют рекурсивным.

Классический пример использования рекурсии, который показывают во всех учебниках по программированию — вычисление факториала числа. Факториал числа N — это произведение всех целых чисел от 1 до N. Например, возьмём число 3 и вычислим его факториал. У нас получится 1 * 2 * 3 = 6. Теперь напишем метод на Java в отдельном классе:

Вызовем рекурсивный метод:

 Factorial f = new Factorial(); // получим число, введенное пользователем int usernumber = Integer.valueOf(editResult.getText().toString()); // вычисляем факториал и выводим результат в текстовой метке textViewInfo.setText("Факториал " + usernumber + " равен " + f.fact(usernumber)); 

Теперь, если вводить числа в текстовом поле, то получим следующие результаты:

Факториал 3 равен 6 Факториал 4 равен 24 Факториал 5 равен 120 и т.д.

Понять, как работает метод, довольно трудно, можно всю голову сломать. Однако попробуем. При вызове метода fact() с аргументом, равным 1, вернётся 1. Тут пока понятно. При других числах возвращается fact(n — 1) * n. Получается, что нужно ещё раз вызвать метод fact(). И так происходит до тех пор, пока не дойдёт до единицы. При этом промежуточные значения умножаются.

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

Следует помнить, что рекурсивные методы требуют больше ресурсов для выполнения и даже может вызвать переполнение памяти при слишком больших значениях.

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

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

Рассмотрим ещё один пример вывода первых элементов массива. Создадим отдельный класс с рекурсивным методом:

 class Recursion < int aValues[]; StringBuilder sb = new StringBuilder(); // Конструктор Recursion(int i) < aValues = new int[i]; >// Рекурсивное отображение элементов массива String printArray(int i) < if (i == 0) return ""; // не забываем про выход из метода else printArray(i - 1); String output = "[" + (i - 1) + "] " + aValues[i - 1] + "\n"; sb.append(output); return sb.toString(); >> public void onClick(View v)

Источник

Русские Блоги

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

Тип данных [] Имя массива = новый тип данных [длина массива], например: int [] arr = new int [10]; 

new заключается в выделении места в памяти. Размер пространства определяется длиной и типом данных массива. После того, как выделение памяти массива завершено, первый адрес памяти будет возвращен имени массива, поэтому имя массива — это ссылка на первый адрес области памяти.

Случай массива

Диаграмма

Дело в том, передать по значению или передать по ссылке

 /*** * Разница между базовыми типами данных и ссылочными типами данных */ public class Demo < // Отображаем число static void show(int a) < a += 5; >static void show(int[] nums) < nums[0] += 5; >public static void main(String[] args) < int a = 10; show(a); System.out.println (a); // 10 не 15 int[] nums = ; show (nums); // Первый адрес массива передается в ссылку на массив в методе System.out.println (nums [0]); // 14 не 9 ////////////////////////////////// // Постоянный объект строки: хранится в пуле констант String str = "hihi"; String str2 = "hihi"; System.out.println (str == str2); // Результат: true show (str); // передаем в метод содержимое переменной str "hihi" System.out.println (str); // Вывод: hihi String str3 = new String("hihi"); String str4 = str3; str3 = "хе-хе"; // хе-хе не существует в пуле констант, объект будет создан в пуле констант, а str3 будет указывать на этот объект System.out.println (str4); // Вывод: hihi > > 

В Java переменные делятся на следующие две категории:

• Для переменных основных типов данных (int, long, double, float, byte, boolean, char) Java является копией переданного значения.
• Для всех объектных переменных Java является копией по ссылке. Фактически, суть передачи ссылочной копии заключается в копировании указателя на адрес (для переменной параметра объекта передать адрес объекта)

Следует отметить, что тип String также является объектной переменной, поэтому он должен быть копией по ссылке. Класс String является окончательным, поэтому этот класс нельзя наследовать или изменять.
Независимо от типа параметра Java всегда передается его копия.

Обмен данными

 /** * Обмен данными */ public class Demo< public static void main(String[] args) < int a = 10, b = 30; System.out.println(a + "," + b); swap(a, b); int[] nums = ; swap(nums); > // Обмен значениями a и b static void swap(int a, int b) < /*int c=a; a=b; b=c; */ a = a + b; b = a - b; a = a - b; System.out.println(a + "," + b); >// Параметры метода: ссылочный тип static void swap(int[] nums) < swap(nums[0], nums[1]); System.out.println (nums [0] + "," + nums [1]); // Значение в массиве в это время не изменится int c = nums[0]; nums[0] = nums[1]; nums[1] = c; System.out.println (nums [0] + "," + nums [1]); // В это время два значения поменялись местами >> 

Улучшено для цикла

 for (имя переменной типа данных: имя массива)

Процесс: считайте числа в массиве последовательно, начиная с позиции 0. Обратной стороной является то, что текущее считанное значение индекса не может быть доступно в теле цикла.

Примеры расширенных циклов for

 public class Demo < public static void main(String[] args) < // Динамически генерировать 10 случайных чисел (1 ~ 100) и читать (печатать) int[] nums = new int[10]; for (int i = 0; i < nums.length; i++) < nums [i] = (int) (Math.random () * 100 + 1); // Генерация случайного числа от 1 до 100 >//Распечатать for (int n : nums) < System.out.print(n + "\t"); >> > 

Двумерный массив

 Тип данных [] [] имя массива = новый тип данных [размер строки] [размер столбца]; Тип данных [] [] Имя массива = новый Тип данных [] [] , , <>, > Тип данных [] [] Имя массива = , , <>, > 

Случай двумерного массива

public class Demo< public static void main(String[] args) < int[][] scores = new int[][], , , , >; // Зациклить одномерный массив: строка for (int i = 0; i < scores.length; i++) < System.out.print («Первый» + (i + 1) + «оценка человека:»); // Зациклить двумерный массив: столбец for (int j = 0; j < scores[i].length; j++) < if (j != scores[i].length - 1) System.out.print(scores[i][j] + ","); else System.out.print(scores[i][j] + "\n"); >> > > 

Дополнение к методу

Рекурсивный метод

Вызовите свой собственный метод самостоятельно.Рекурсивный метод требует двух точек: одна — это рекурсивная формула, а другая — рекурсивное условие.

Пример 1: Рекурсивно найти факториал

 /** * Рекурсивно найти факториал * * @param n */ private static int fun(int n) < if (n == 0 || n == 1) < return 1; >return n * fun(n - 1); > 

 /** * Классический кролик * * @param x * @return */ public static int getNums(int x) < int nums = 1; if (x == 1 || x == 2) < return nums; >return getNums(x - 1) + getNums(x - 2); > 

Тестовый сайт

Когда объект передается в качестве параметра методу, метод может изменять свойства объекта и возвращать измененный результат. Итак, он передается по значению или по ссылке? (Передать по значению или по ссылке)

Это значение пройти. Вызов методов на языке Java поддерживает только передачу значений параметров. Когда экземпляр объекта передается методу в качестве параметра, значение параметра является ссылкой на объект. Свойства объекта могут быть изменены в процессе вызова, но изменение ссылки на объект не повлияет на вызывающего.

Источник

Рекурсия в Java: пример программы + детальный обзор

В языке Java поддерживается рекурсия — процесс определения чего-либо отно­сительно самого себя.

Применительно к программированию на Java рекурсия — это средство, которое позволяет методу вызывать самого себя. Такой метод назы­вается рекурсивным.

Классическим примером рекурсии служит вычисление факториала числа. Факториал числа N — это произведение всех целых чисел от 1 до N. Например ,факториал числа 3 равен 1 х 2 х 3, т.е. 6. Ниже показано, как вычислить факториал, используя рекурсивный метод.

Ниже приведен результат, выводимый этой программой.

Тем, кто незнаком с рекурсивными методами, принцип действия метода fact() может быть не совсем понятным.

Метод fact() действует следующим образом. Когда этот метод вызывается со значением 1 своего аргумента, возвращается зна­чение 1. В противном случае возвращается произведение fact(n — 1) * n .

Для вычисления этого выражения метод fact() вызывается со значением n — 1 своего аргумента. Этот процесс повторяется до тех пор, пока n не станет равным 1, после чего начнется возврат из последовательных вызовов метода fact().

Для того чтобы стал понятнее принцип действия рекурсивного метода fact(), обратимся к небольшому примеру.

Для расчета факториала числа З вслед за пер­вым вызовом метода fact() происходит второй вызов этого метода со значением 2 его аргумента.

Это, в свою очередь, приводит к третьему вызову метода fact() со значением 1 его аргумента. Возвращаемое из этого вызова значение 1 затем ум­ножается на 2 (т.е. значение n при втором вызове метода).

Полученный результат ,равный 2 , возвращается далее исходному вызову метода fact() и умножается на 3 (исходное значение n).

В конечном итоге получается искомый результат, равный 6. В метод fact() можно было бы ввести вызовы метода println(), чтобы отобра­жать уровень каждого вызова и промежуточные результаты вычисления фактори­ала заданного числа.

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

При каждом возврате из вызова рекурсивного методапрежние локальные переменные и параметры удаляются из стека, а выполнение продолжается с точки вызова в самом методе.

Рекурсивные методы выполняют дей­ствия, которые можно сравнить с раскладыванием и складыванием телескопа.

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

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

В таком случаев исполняющей системе Jаvа возникнет исключение. Но подобная ситуация не воз­никнет, если не выпустить рекурсивный метод из-под контроля.

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

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

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

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

Поэтому на стадии разработки рекурсивных методов рекомендуется как можно чаще делать вызовы метода println(), чтобы сле­дить за происходящим и прерывать выполнение при обнаружении ошибки.

Рассмотрим еще один пример организации рекурсии. В данном примере рекур­сивный метод рrintArrау() выводит первые i элементов из массива values.

Источник