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

Java. Рекурсия. Примеры решения задач. Преимущества и недостатки рекурсии

Рекурсия. Примеры решения задач. Преимущества и недостатки рекурсии

Поиск на других ресурсах:

1. Что такое рекурсия? Что называется рекурсией?

В теории алгоритмов дается следующее определение рекурсии: рекурсия – это такой способ задания функции, при котором результат возврата из функции для данного значения аргумента определяется на основе результата возврата из той же функции для предыдущего (меньшего или большего) значения аргумента.

Другими словами, рекурсия – это вызов функции самой себя для перехода к следующему шагу рекурсии. Чтобы следующий шаг рекурсии отличался от предыдущего, значение как минимум одного из параметров функции должно изменяться в процессе рекурсивного вызова.

2. Объяснение к реализации задач на рекурсию. Как правильно организовать рекурсивный вызов функции?

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

Чтобы циклический процесс превратить в рекурсивный, нужно уметь определить (выделить) три важных момента:

• условие прекращения рекурсивного процесса. Например, если счетчик или итератор с именем k изменяется от 1 до 10 в возрастающем порядке, то условие прекращения есть достижение значения k =10. Условие прекращения указывается в операторе return ;
• формулу следующего элемента или итератора, который используется в рекурсивном процессе. Эта формула указывается в операторе return ;
• перечень параметров, которые передаются в рекурсивную функцию. Один из параметров обязательно есть итератор (счетчик), изменяющий свое значение. Другие параметры являются дополнительными, например, ссылка на обрабатываемый массив.

3. Поиск суммы элементов массива. Пример

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

Задача. Задан массив чисел A . Разработать рекурсивную функцию, которая находит сумму элементов массива:

где n – количество элементов массива. Программный код функции следующий:

// рекурсия - сумма элементов массива static int Sum(int i, int[] A) <  if (i==(A.length-1))  return A[i];  return A[i] + Sum(i+1,A); >

В вышеприведенном коде функция получает два параметра. Первый параметр i есть значением текущего индекса, который изменяет свое значение при каждом рекурсивном вызове. Второй параметр A – массив, элементы которого суммируются.

Последний элемент массива имеет индекс A.length-1 . Достижение функцией последнего элемента массива есть выходом из нее. Поэтому, в тексте функции Sum() указывается условие прекращения рекурсивного процесса:

if (i==(A.length-1))  return A[i];

В языке Java массив есть экземпляром (объектом) класса, поэтому количество элементов в массиве определяется свойством length . Это есть удобным, поскольку не нужно передавать размерность массива в виде параметра (в отличие от некоторых других языков программирования).

Поскольку, осуществляется сумма текущего значения A[i] со следующими, то указывается строка

// A[i] - текущее значение, Sum(i+1,A) – следующее значение в массиве return A[i] + Sum(i+1,A);

где Sum(i+1, A) означает следующее значение массива A , которое будет вычислено на следующем (нижнем) уровне рекурсивного вызова. Параметр i+1 указывает, что на следующем уровне рекурсии будут взяты следующий за данным элемент массива.

Использование функции Sum() в другом программном коде может быть следующим:

int[] A = < 3, 12, 10, 11 >; int sum; sum = Sum(0,A); // sum = 36

4. Вычисление факториала числа – n! . Пример

В примере разработана рекурсивная функция, которая находит факториал заданного числа n

Программный код функции следующий:

// вычисление факториала числа n int Fact(int n) <  if (n==1)  return 1; // условие завершения рекурсивного процесса  else  return n*Fact(n-1); // Fact(n-1) - результат следующих вызовов функции >

В данной функции происходит рекурсивный вызов функции Fact() с параметром n , который изменяется от n до 1 в порядке убывания. Рекурсивный процесс завершается при n = 1.

При возврате на уровень выше возвращается текущее значение n и результат вычислений при следующих рекурсивных вызовах:

return n*Fact(n-1);

Использование функции в другом программном коде:

int fact; fact = Fact(7); // fact = 5040

5. Программа нахождения наибольшего общего делителя по алгоритму Евклида. Пример

В примере определяется наибольший общий делитель по формуле Евклида:

Программный код функции следующий:

// НОД - Алгоритм Евклида int MaxDivisor(int n, int m) <  if (n==m) return n;  else  if (n>m) return MaxDivisor(n-m, m);  else  return MaxDivisor(n, m-n); // n >

Использование функции MaxDivisor

int md; md = MaxDivisor(28,20); // md = 4

6. Вычислить n -й член последовательности чисел Фибоначчи. Пример

Последовательность чисел Фибоначчи имеет вид:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

В последовательности чисел Фибоначчи каждое следующее число n определяется как сумма двух предшествующих чисел: (n-1) + (n-2) . Поэтому, в формуле рекурсивного процесса может быть вызов суммы двух функций а не одной. Прекращение рекурсивного процесса достигается, если значение n =0.

Ниже приведен текст функции GetNFibonacci()

// Определение n-го числа Фибоначчи static int GetNFibonacci(int n) <  if (n>1)  return GetNFibonacci(n-2)+GetNFibonacci(n-1); // формула Фибоначчи  else  if (n==1)  return 1;  else  return 0; // если n==0 >

Использование метода GetNFibonacci() в другом программном коде:

int n; n = GetNFibonacci(10); // n = 55

7. Преимущества и недостатки использования рекурсии

Рекурсию часто сравнивают с итерацией. Организация циклического процесса с помощью рекурсии имеет свои преимущества и недостатки.

Можно выделить следующие взаимосвязанные преимущества рекурсии:

• естественность (натуральность) выражения сложных, на первый взгляд, алгоритмов.
• рекурсивный алгоритм более читабелен в сравнении с итерационным;
• для многих распространенных задач рекурсию более легче реализовать чем итерацию. Рекурсия хорошо подходит для реализации алгоритмов обхода списков, деревьев, графов и т.д.

Недостатки рекурсии состоят в следующем:

• по сравнению с итерацией многократный вызов рекурсивной функции работает дольше. Это связано с тем, что при вызове рекурсивного метода его параметры копируются в стек. Также запоминаются временные значения локальных внутренних переменных. При завершении вызова рекурсивной функции предыдущие значения параметров вытягиваются из стека, что приводит к лишним операциям. Итерационный алгоритм для такой же задачи работает быстрее;
• для рекурсивного процесса нужно больше памяти чем для итерации. Это связано с тем, что при рекурсивном вызове нужно сохранять предыдущее значение внутренних переменных вызывающей функции, чтобы по завершении рекурсивного вызова восстановить ее выполнение. Таким образом, если рекурсивная функция вызывается много раз, то это может привести к чрезмерно большому использованию памяти.

Связанные темы

Источник

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

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

Тип данных [] Имя массива = новый тип данных [длина массива], например: 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 поддерживает только передачу значений параметров. Когда экземпляр объекта передается методу в качестве параметра, значение параметра является ссылкой на объект. Свойства объекта могут быть изменены в процессе вызова, но изменение ссылки на объект не повлияет на вызывающего.

Источник