Этот подробный учебник по рекурсии в Java объясняет, что такое рекурсия с примерами, типами и связанными с ней понятиями, а также рассказывает о рекурсии и итерации:
Из наших предыдущих уроков по Java мы видели итеративный подход, при котором мы объявляем цикл и затем итеративно проходим через структуру данных, беря по одному элементу за раз.
Мы также видели условный поток, в котором мы сохраняем одну переменную цикла и повторяем часть кода до тех пор, пока переменная цикла не выполнит условие. Когда дело доходит до вызовов функций, мы также изучили итеративный подход для вызовов функций.
В этом учебнике мы рассмотрим другой подход к программированию, а именно рекурсивный подход.
Что такое рекурсия в Java?
Рекурсия - это процесс, при котором функция или метод вызывают себя снова и снова. Функция, которая вызывается снова и снова прямо или косвенно, называется "рекурсивной функцией".
Мы рассмотрим различные примеры для понимания рекурсии. Теперь давайте посмотрим синтаксис рекурсии.
Синтаксис рекурсии
Любой метод, реализующий рекурсию, состоит из двух основных частей:
- Вызов метода, который может вызывать сам себя, т.е. рекурсивный
- Предварительное условие, которое остановит рекурсию.
Обратите внимание, что предусловие необходимо для любого рекурсивного метода, поскольку, если мы не прервем рекурсию, она будет продолжаться бесконечно и приведет к переполнению стека.
Общий синтаксис рекурсии выглядит следующим образом:
methodName (T parameters...) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters...); //recursive call } Обратите внимание, что предусловие также называется базовым условием. Подробнее о базовом условии мы поговорим в следующем разделе.
Понимание рекурсии в Java
В этом разделе мы попытаемся понять процесс рекурсии и увидеть, как он происходит. Мы узнаем о базовом условии, переполнении стека, увидим, как можно решить конкретную задачу с помощью рекурсии и другие подобные детали.
Базовое условие рекурсии
При написании рекурсивной программы мы должны сначала предоставить решение для базового случая. Затем мы выражаем большую проблему в терминах меньших проблем.
В качестве пример, Мы можем взять классическую задачу вычисления факториала числа. Дано число n, нужно найти факториал числа n, обозначаемый n!
Теперь давайте реализуем программу для вычисления факториала n (n!) с помощью рекурсии.
public class Main{ static int fact(int n) { if (n == 1) // базовое условие return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } Выход
В этой программе мы видим, что условие (n<=1) является базовым условием, и когда это условие достигается, функция возвращает 1. Часть else функции является рекурсивным вызовом. Но при каждом вызове рекурсивного метода n уменьшается на 1.
Таким образом, мы можем заключить, что в конечном итоге значение n станет 1 или меньше 1, и в этот момент метод вернет значение 1. Это базовое условие будет достигнуто, и функция остановится. Обратите внимание, что значение n может быть любым, если оно удовлетворяет базовому условию.
Решение проблем с помощью рекурсии
Основная идея использования рекурсии заключается в том, чтобы выразить большую проблему в терминах меньших проблем. Кроме того, нам нужно добавить одно или несколько базовых условий, чтобы мы могли выйти из рекурсии.
В этой программе мы выражали факториал n (n!) в терминах меньших значений и имели базовое условие (n <=1), так что когда n достигает 1, мы можем выйти из рекурсивного метода.
Ошибка переполнения стека при рекурсии
Мы знаем, что при вызове любого метода или функции состояние функции хранится в стеке и извлекается при возврате функции. Стек используется и для рекурсивного метода.
Но в случае с рекурсией может возникнуть проблема, если мы не определим базовое условие или если базовое условие каким-то образом не будет достигнуто или выполнено. Если такая ситуация произойдет, то может возникнуть переполнение стека.
Рассмотрим приведенный ниже пример факториальной нотации.
Здесь мы задали неверное базовое условие, n==100.
public class Main { static int fact(int n) { if (n == 100) // базовое условие, приводящее к переполнению стека return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } Поэтому, когда n> 100, метод вернет 1, но рекурсия не прекратится. Значение n будет продолжать уменьшаться бесконечно, поскольку нет другого условия, чтобы остановить его. Это будет продолжаться до переполнения стека.
Другим случаем будет, когда значение n <100. В этом случае метод также никогда не выполнит базовое условие и приведет к переполнению стека.
Примеры рекурсии в Java
В этом разделе мы реализуем следующие примеры с использованием рекурсии.
#1) Серия Фибоначчи с использованием рекурсии
Ряд Фибоначчи задается,
1,1,2,3,5,8,13,21,34,55,…
Приведенная выше последовательность показывает, что текущий элемент является суммой двух предыдущих элементов. Кроме того, первый элемент в ряду Фибоначчи равен 1.
В общем случае, если n - текущее число, то оно задается суммой (n-1) и (n-2). Поскольку текущий элемент выражается в терминах предыдущих элементов, мы можем выразить эту задачу с помощью рекурсии.
Программа для реализации ряда Фибоначчи приведена ниже:
public class Main { //метод вычисления ряда Фибоначчи static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { int number = 10; //вывод первых 10 чисел ряда Фибоначчи System.out.println ("Серия Фибоначчи: первые 10 чисел:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Выход
#2) Проверьте, является ли число палиндромом, используя рекурсию
Палиндром - это последовательность, которая одинакова, если читать ее слева направо или справа налево.
Если взять число 121, то видно, что при чтении слева направо и справа налево оно одинаково. Следовательно, число 121 - палиндром.
Возьмем другое число, 1242. Когда мы читаем его слева направо, оно равно 1242, а когда справа налево - 2421. Таким образом, это не палиндром.
Мы реализуем программу палиндрома, переворачивая цифры чисел и рекурсивно сравнивая заданное число с его перевернутым представлением.
Приведенная ниже программа реализует программу проверки палиндрома.
import java.io.*; import java.util.*; public class Main { // проверяем, содержит ли num только одну цифру public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } // функция утилиты палиндрома public static int isPalindrome_util (int num, int revNum) throws Exception { // базовое условие; return if num=0 if (num == 0) { return revNum; } else { // вызовфункция утилиты рекурсивно revNum = isPalindrome_util(num / 10, revNum); } // Проверяем, равна ли первая цифра num и revNum if (num % 10 == revNum % 10) { // если да, то revNum будет двигаться вместе с num return revNum / 10; } else { // exit throw new Exception(); } } } // Метод проверки палиндромности заданного числа с помощью функции утилиты palindrome public static int isPalindrome(int num) throwsException { if (num <0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Да, данное число " + n + " является палиндромом."); } catch (Exception e) { System.out.println("Нет, данное число " + n + " не является палиндромом."); } n = 1221; try { isPalindrome(n);System.out.println("Да, данное число " + n + " является палиндромом."); } catch (Exception e) { System.out.println("Нет, данное число " + n + " не является палиндромом."); } } } } Выход
#3) Обратная рекурсия строк Java
Взяв строку "Hello", мы должны перевернуть ее так, чтобы в результате получилась строка "olleH".
Для этого используется рекурсия. Начиная с последнего символа строки, мы рекурсивно выводим каждый символ, пока все символы в строке не будут исчерпаны.
Приведенная ниже программа использует рекурсию для реверсирования заданной строки.
class String_Reverse { //рекурсивный метод для разворота заданной строки void reverseString(String str) { //базовое условие; возврат, если строка равна null или содержит 1 или менее символов if ((str==null))} } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Заданная строка: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Перевернутая строка: "); obj.reverseString(inputstr); } } } Выход
#4) Бинарный поиск Рекурсия Java
Алгоритм бинарного поиска - это известный алгоритм поиска. В этом алгоритме, задав отсортированный массив из n элементов, мы ищем в этом массиве заданный ключевой элемент. В начале мы делим массив на две половины, находя средний элемент массива.
Затем, в зависимости от того, где находится ключевая середина, мы ограничиваем поиск в первой или второй половине массива. Таким образом, один и тот же процесс повторяется до тех пор, пока местоположение ключевых элементов не будет найдено.
Здесь мы реализуем этот алгоритм с помощью рекурсии.
import java.util.*; class Binary_Search { // рекурсивный бинарный поиск int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { // вычисляем середину массива int mid = left + (right - left) / 2; // если ключ находится в середине, возвращаем середину if (numArray[mid] == key) return mid; // если ключ key) return binarySearch(numArray, left, mid - 1, key); // иначе рекурсивно ищем в массивеправый подмассив return binarySearch(numArray, mid + 1, right, key); } // в массиве нет элементов, return -1 return -1; } } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); // объявляем и печатаем массив int numArray[] = { 4,6,12,16,22}; System.out.println("Данный массив : " + Arrays.toString(numArray)); int len = numArray.length; // длина массиваint key = 16; //ключ для поиска int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Элемент " + key + " отсутствует"); else System.out.println("Элемент " + key + " найден по индексу " + result); } } Выход
#5) Найти минимальное значение в массиве с помощью рекурсии
Используя рекурсию, мы также можем найти минимальное значение в массиве.
Ниже приведена Java-программа для нахождения минимального значения в массиве.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //возврат первого элемента, если элемент только один, или минимального из элементов массива return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1, n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Данный массив : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Минимальный элемент массива: " + getMin(numArray, 0, n) + "\n"); } } Выход
Это некоторые из примеров рекурсии. Помимо этих примеров, множество других проблем в программном обеспечении могут быть реализованы с помощью рекурсивных методов.
Типы рекурсии
Рекурсия бывает двух типов в зависимости от того, когда происходит вызов рекурсивного метода.
К ним относятся:
#1) Хвостовая рекурсия
Когда вызов рекурсивного метода является последним оператором, выполняемым внутри рекурсивного метода, это называется "хвостовой рекурсией".
При хвостовой рекурсии оператор рекурсивного вызова обычно выполняется вместе с оператором возврата метода.
Общий синтаксис хвостовой рекурсии приведен ниже:
methodName ( T parameters...){ { if (base_condition == true) { return result; } return methodName (T parameters ...) //хвостовая рекурсия } #2) Рекурсия головы
Головная рекурсия - это любая рекурсия, которая не является хвостовой рекурсией. Поэтому даже общая рекурсия является опережающей рекурсией.
Синтаксис головной рекурсии выглядит следующим образом:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Рекурсия и итерация в Java
| Рекурсия | Итерация |
|---|---|
| Рекурсия - это процесс, в котором метод вызывает сам себя многократно, пока не будет выполнено базовое условие. | Итерация - это процесс, в ходе которого часть кода выполняется конечное число раз или до тех пор, пока не будет выполнено условие. |
| Является ли приложение для функций. | Применяется для петель. |
| Хорошо работает при небольшом размере кода. | Хорошо работает при большом размере кода. |
| Использует больше памяти, так как каждый рекурсивный вызов заносится в стек | Используется сравнительно меньше памяти. |
| Сложность отладки и обслуживания | Легче отлаживать и поддерживать |
| Приводит к переполнению стека, если базовое условие не указано или не достигнуто. | Может выполняться бесконечно, но в конечном итоге прекращает выполнение при любых ошибках памяти |
| Временная сложность очень высока. | Временная сложность относительно невелика. |
Часто задаваемые вопросы
Вопрос #1) Как работает рекурсия в Java?
Ответ: При рекурсии рекурсивная функция вызывает сама себя многократно, пока не будет выполнено базовое условие. Память для вызываемой функции помещается в стек на вершине памяти для вызывающей функции. Для каждого вызова функции создается отдельная копия локальных переменных.
Q #2) Почему используется рекурсия?
Ответ: Рекурсия используется для решения тех задач, которые могут быть разбиты на более мелкие, и вся задача может быть выражена в терминах более мелкой задачи.
Рекурсия также используется для тех задач, которые слишком сложны для решения с помощью итерационного подхода. Кроме задач, для которых временная сложность не является проблемой, используйте рекурсию.
Q #3) Каковы преимущества рекурсии?
Ответ:
Преимущества рекурсии включают:
- Рекурсия уменьшает избыточный вызов функции.
- Рекурсия позволяет нам решать проблемы проще, чем итерационный подход.
Вопрос # 4) Что лучше - рекурсия или итерация?
Ответ: Рекурсия повторяет вызовы до тех пор, пока не будет достигнута базовая функция. Таким образом, происходит перерасход памяти, поскольку память для каждого вызова функции помещается в стек.
С другой стороны, итерация не требует больших затрат памяти. Рекурсия выполняется медленнее, чем итеративный подход. Рекурсия уменьшает размер кода, в то время как итеративный подход делает код большим.
Q #5) В чем преимущества рекурсии перед итерацией?
Ответ:
- Рекурсия делает код более понятным и коротким.
- Рекурсия лучше итеративного подхода для таких задач, как Ханойская башня, обход деревьев и т.д.
- Поскольку при каждом вызове функции память заносится в стек, рекурсия использует больше памяти.
- Рекурсия работает медленнее, чем итеративный подход.
Заключение
Рекурсия - очень важная концепция в программном обеспечении, независимо от языка программирования. Рекурсия в основном используется при решении задач, связанных со структурой данных, таких как ханойские башни, обход деревьев, связные списки и т.д. Хотя она занимает больше памяти, рекурсия делает код проще и понятнее.
В этом учебнике мы рассмотрели все о рекурсии, а также привели множество примеров программирования для лучшего понимания концепции.