Този задълбочен урок по рекурсия в Java обяснява какво е рекурсия с примери, типове и свързани концепции. Той също така обхваща рекурсия срещу итерация:
В предишните уроци по Java видяхме итеративния подход, при който декларираме цикъл и след това преминаваме през структура от данни по итеративен начин, като вземаме по един елемент наведнъж.
Видяхме също така условния поток, при който отново запазваме една променлива от цикъла и повтаряме част от кода, докато променливата от цикъла не изпълни условието. Когато става въпрос за извикване на функции, изследвахме също така итеративния подход за извикване на функции.
В този урок ще обсъдим един различен подход към програмирането, а именно рекурсивния подход.
Какво представлява рекурсията в Java?
Рекурсията е процес, при който дадена функция или метод се извиква отново и отново. Тази функция, която се извиква отново и отново пряко или непряко, се нарича "рекурсивна функция".
Ще видим различни примери, за да разберем рекурсията. Сега нека видим синтаксиса на рекурсията.
Синтаксис на рекурсията
Всеки метод, който реализира рекурсия, има две основни части:
- Извикване на метод, който може да се извика сам, т.е. рекурсивен
- Предварително условие, което ще спре рекурсията.
Обърнете внимание, че предварително условие е необходимо за всеки рекурсивен метод, тъй като ако не прекъснем рекурсията, тя ще продължи да се изпълнява безкрайно и ще доведе до препълване на стека.
Общият синтаксис на рекурсията е следният:
methodName (T parameters...) { if (precondition == true) //предпоставка или базово условие { return result; } return methodName (T parameters...); //рекурсивно извикване } Обърнете внимание, че предварителното условие се нарича още базово условие. Ще обсъдим повече за базовото условие в следващия раздел.
Разбиране на рекурсията в Java
В този раздел ще се опитаме да разберем процеса на рекурсия и да видим как протича той. Ще научим за базовото условие, препълването на стека, ще видим как даден проблем може да бъде решен с рекурсия и други подобни подробности.
Базово условие за рекурсия
Докато пишем рекурсивната програма, първо трябва да дадем решение за базовия случай. След това изразяваме по-големия проблем в термините на по-малки проблеми.
Като пример, Можем да разгледаме класическа задача за изчисляване на факториал на число. При дадено число n трябва да намерим факториал на n, означен с n!
Сега нека реализираме програмата за изчисляване на n-факториала (n!), като използваме рекурсия.
public class Main{ static int fact(int n) { if (n == 1) // base condition 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; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //callполезната функция рекурсивно 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) { //базово условие; връща се, ако низът е нулев или с 1 или по-малко символа if ((str==null)} } } клас 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 { // recursive binary search int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray[mid] == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursive search in theдесен подмасив 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...) //tail recursion } #2) Рекурсия на главата
Рекурсия начело е всеки рекурсивен подход, който не е рекурсия на опашката. Така че дори общата рекурсия е рекурсия напред.
Синтаксисът на рекурсията в главата е следният:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Рекурсия срещу итерация в Java
| Рекурсия | Итерация |
|---|---|
| Рекурсията е процес, при който даден метод се извиква многократно, докато не бъде изпълнено базово условие. | Итерацията е процес, при който дадена част от кода се изпълнява многократно за определен брой пъти или докато се изпълни дадено условие. |
| Дали приложението е за функции. | Прилага се за цикли. |
| Работи добре при по-малък размер на кода. | Работи добре за по-голям размер на кода. |
| Използва повече памет, тъй като всяко рекурсивно извикване се избутва в стека | Използва се сравнително по-малко памет. |
| Трудно отстраняване на грешки и поддръжка | По-лесно отстраняване на грешки и поддръжка |
| Води до препълване на стека, ако базовото условие не е посочено или не е достигнато. | Може да се изпълнява безкрайно, но в крайна сметка ще спре изпълнението при грешки в паметта. |
| Времевата сложност е много висока. | Времевата сложност е сравнително по-ниска. |
Често задавани въпроси
В #1) Как работи рекурсията в Java?
Отговор: При рекурсията рекурсивната функция се извиква многократно, докато не бъде изпълнено базово условие. Паметта за извиканата функция се премества в стека в горната част на паметта за извикващата функция. За всяко извикване на функция се прави отделно копие на локалните променливи.
Q #2) Защо се използва рекурсия?
Отговор: Рекурсията се използва за решаване на онези задачи, които могат да бъдат разделени на по-малки и целият проблем може да бъде изразен като по-малък проблем.
Рекурсията се използва и за онези проблеми, които са твърде сложни, за да бъдат решени чрез итеративен подход. Освен за проблеми, за които времевата сложност не е проблем, използвайте рекурсия.
Q #3) Какви са предимствата на рекурсията?
Отговор:
Предимствата на рекурсията включват:
- Рекурсията намалява излишното извикване на функция.
- Рекурсията ни позволява да решаваме лесно проблеми в сравнение с итеративния подход.
Въпрос #4) Кое е по-добро - рекурсията или итерацията?
Отговор: Рекурсията прави многократни извиквания, докато се достигне до базовата функция. По този начин се увеличава паметта, тъй като паметта за всяко извикване на функция се избутва в стека.
От друга страна, итерацията няма много разходи за памет. Изпълнението на рекурсията е по-бавно от итеративния подход. Рекурсията намалява размера на кода, докато итеративният подход го прави голям.
Q #5) Какви са предимствата на рекурсията пред итерацията?
Отговор:
- Рекурсията прави кода по-ясен и по-кратък.
- Рекурсията е по-добра от итеративния подход за задачи като кулата на Ханой, обхождане на дървета и др.
- Тъй като при всяко извикване на функция паметта се премества в стека, рекурсията използва повече памет.
- Изпълнението на рекурсията е по-бавно, отколкото при итеративния подход.
Заключение
Рекурсията е много важна концепция в софтуера, независимо от езика за програмиране. Рекурсията се използва най-вече при решаване на проблеми със структури от данни, като кули на Ханой, обхождане на дървета, свързани списъци и т.н. Въпреки че отнема повече памет, рекурсията прави кода по-прост и ясен.
В този урок разгледахме всичко за рекурсията. Също така приложихме множество примери за програмиране за по-добро разбиране на концепцията.