Рекурсия 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, рекурсия, задачи