На нашем сайте мы используем cookie для сбора информации технического характера и обрабатываем IP-адрес вашего местоположения. Продолжая использовать этот сайт, вы даете согласие на использование файлов cookies. Здесь вы можете узнать, как мы пользуемся файлами cookies.
Я согласен
логотип upread.ru

Рекурсия Java в примерах


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

Рекурсия – это вызов самого себя. Самой функции. Но вызывать надо с немного другими параметрами и предусмотреть возможность выхода. На самом деле разобравшись, вы будете применять её на автомате.

Палиндром циклом Java

Задача: необходимо узнать, является ли данное слово палиндромом, то есть читается ли аналогично слева направо и справа налево. Это такие слова как «довод», «заказ» и так далее. Как бы мы решили эту задачу с помощью цикла for? Например, вот так:

static boolean isPalindromeFor(String str) {
boolean flag = true;
for (int i=0 ; i<str.length()/2; i++) {			
if (str.charAt(i) != str.charAt(str.length() - i -1)) flag = false;	 
}		  
return flag;
}
Тут все очень просто: задаем флаг (изначально считаем, что слово палиндром) и пробегаем по нему до середины, попутно сравнивая элементы, находящиеся на противоположных местах. И если какие-то не совпадают, то в результате получаем false. А как это же сделать рекурсией?

Палиндром рекурсией Java

Во-первых, надо немного поменять стиль мышления. Составьте такой код:

static boolean isPalindromeRec(String str) {
	 
if (str.charAt(0) != str.charAt(str.length() - 1))  return false;
 
else   return true;

}
Это условие для первого и последнего элементов строки. Но, постойте, а с чего мы это взяли? Ну как же, скажет вы – вот строка, вот берем первый, последний. Стоп, а что нам мешает передавать в этот же метод другую строку? Уменьшенную с двух сторон? Ничего. Вот так:

static boolean isPalindromeRec(String str) {
	 
if (str.charAt(0) != str.charAt(str.length() - 1))  return false;
 
return isPalindromeRec(str.substring(1, str.length() - 1));

}
Однако, такой код не заработает – у нас нет выхода для всех ситуаций. Нам надо предусмотреть, когда выводить true? А очень просто – когда мы обрежем строку с двух сторон полностью:

static boolean isPalindromeRec(String str) {
if (str.length() <= 1)  return true;
		 
if (str.charAt(0) != str.charAt(str.length() - 1))  return false;
		 
return isPalindromeRec(str.substring(1, str.length() - 1));
}
И теперь все работает! Запомните: у рекурсии обязательно должен быть выход. А теперь разберём другой пример.

Сокращение дроби циклом

Имеем код

public static void divide(double m, double n) {
		double q, i;
		System.out.println ("Результат: ");
		if (m > n) {
		    q = n;
		}
		else q = m;

		for (i=2; i<q; i++) {
			
		if (m%i==0 && n%i==0)	{			
			m /= i;
			n /= i;
		}		
		}
		System.out.println (m+"/"+n);
		}
Этот код по задумке автора сокращает дроби. Как видим, здесь просто берется цикл, начиная от двойки проходится до старшего числа и если оба делятся (числитель и знаменатель), то делим. А как же преобразовать в рекурсию?

Сокращение дроби рекурсией

В этом случае в первоначальный метод добавляем еще один параметр – переменную i типа int. Сам метод тоже меняем, он будет не void, а возвращать int. Хоть нам и не надо то, что он возвращает, но для рекурсии требуется выход из цикла, а return – отличный выход. Итак, вот код:

    static int rec(int i, double m, double n) {    	
	        int result;
	        	  if (i<=n) {	        		  
	        		  if (m%i==0 && n%i==0)  {        		  
	  	        	m /= i;
	  				n /= i;	
	        		  }
	        		  i++;
	  				  result = rec(i, m, n);
	  				   return result;
	  	        }        		       	    
	        System.out.println (m+"/"+n);
	        return 1;	       
	    }
Обратите внимание, что он очень похож на тот, что выше. Мы добавили условие выхода из рекурсии и вызываем снова функцию rec, если деление удалось.

Если вам требуется помощь по Java, то смело пишите мне – я за небольшую плату и с удовольствием помогу вам. От простых задач и до сложных проектов.




тегизаметки, java, рекурсия, задачи





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




C# Visual Studio и базы данных: подключаем Microsoft SQL Server Compact
Воспроизведение музыки в формате mp3 на Java


© upread.ru 2013-2019
При перепечатке активная ссылка на сайт обязательна.
Задать вопрос
письмо
Здравствуйте! Вы можете задать мне любой вопрос. Если не получается отправить сообщение через эту форму, то пишите на почу up777up@yandex.ru
Отправляя сообщение я подтверждаю, что ознакомлен и согласен с политикой конфиденциальности данного сайта.