1. Въведение
В тази статия ще се съсредоточим върху основна концепция на всеки език за програмиране - рекурсия.
Ще обясним характеристиките на рекурсивна функция и ще покажем как да използваме рекурсията за решаване на различни проблеми в Java.
2. Разберете рекурсията
2.1. Дефиницията
В Java механизмът за извикване на функции поддържа възможността за само извикване на метод . Тази функционалност е известна като рекурсия .
Да предположим например, че искаме да сумираме целите числа от 0 до някаква стойност n :
public int sum(int n) { if (n >= 1) { return sum(n - 1) + n; } return n; }Има две основни изисквания за рекурсивна функция:
- Условие за спиране - функцията връща стойност, когато е изпълнено определено условие, без допълнително рекурсивно повикване
- Рекурсивното повикване - функцията се извиква с вход, който е стъпка по-близо до условието за спиране
Всяко рекурсивно повикване ще добави нов кадър към стековата памет на JVM. Така че, ако не обърнем внимание колко дълбоко може да се гмурка рекурсивният ни разговор, може да възникне изключение без памет.
Този потенциален проблем може да бъде предотвратен чрез използване на оптимизация на рекурсията на опашката.
2.2. Рекурсия на опашката срещу рекурсия на главата
Ние наричаме рекурсивна функция като рекурсивна опашка, когато рекурсивното повикване е последното нещо, което функцията изпълнява. В противен случай това е известно като рекурсия на главата .
Нашето изпълнение по-горе на функцията sum () е пример за рекурсия на главата и може да бъде променено на рекурсия на опашката:
public int tailSum(int currentSum, int n) { if (n <= 1) { return currentSum + n; } return tailSum(currentSum + n, n - 1); }При рекурсията на опашката рекурсивното извикване е последното нещо, което методът прави, така че не остава нищо за изпълнение в рамките на текущата функция.
По този начин логично няма нужда да се съхранява рамката на стека на текущата функция.
Въпреки че компилаторът може да използва тази точка за оптимизиране на паметта, трябва да се отбележи, че Java компилаторът засега не оптимизира за рекурсия на опашката .
2.3. Рекурсия срещу итерация
Рекурсията може да помогне за опростяване на изпълнението на някои сложни проблеми, като направи кода по-ясен и по-четлив.
Но както вече видяхме, рекурсивният подход често изисква повече памет, тъй като изискваната памет на стека се увеличава с всяко рекурсивно повикване.
Като алтернатива, ако можем да решим проблем с рекурсия, можем да го решим и с итерация.
Например, нашият метод sum може да бъде реализиран с помощта на итерация:
public int iterativeSum(int n) { int sum = 0; if(n < 0) { return -1; } for(int i=0; i<=n; i++) { sum += i; } return sum; }В сравнение с рекурсията, итеративният подход може потенциално да даде по-добри резултати. Като се има предвид това, итерацията ще бъде по-сложна и по-трудна за разбиране в сравнение с рекурсията, например: обхождане на двоично дърво.
Правилният избор между рекурсия на главата, рекурсия на опашката и итеративен подход зависи от конкретния проблем и ситуация.
3. Примери
Сега, нека се опитаме да разрешим някои проблеми по рекурсивен начин.
3.1. Намиране на N-та степен на десет
Да предположим, че трябва да изчислим n- тата степен на 10. Тук нашият вход е n. Мислейки по рекурсивен начин, първо можем да изчислим (n-1) -та степен на 10 и да умножим резултата по 10.
След това, за да се изчисли (n-1) -та степен на 10 ще бъде (n-2) -та степен на 10 и да се умножи този резултат по 10 и т.н. Ще продължим така, докато стигнем до точка, в която трябва да изчислим (nn) -та степен на 10, което е 1.
Ако искахме да приложим това в Java, щяхме да напишем:
public int powerOf10(int n) { if (n == 0) { return 1; } return powerOf10(n-1) * 10; }3.2. Намиране на N-ти елемент на последователността на Фибоначи
Започвайки с 0 и 1 , последователността на Фибоначи е поредица от числа, където всяко число се дефинира като сбор от двете числа, които го продължават : 0 1 1 2 3 5 8 13 21 34 55 ...
И така, като се има предвид числото n , нашият проблем е да намерим n- ия елемент на последователността на Фибоначи . За да приложим рекурсивно решение, трябва да разберем условието за спиране и рекурсивното повикване .
За щастие наистина е лесно.
Нека наречем е (н) на п -тата стойност на последователността. Тогава ще имаме f (n) = f (n-1) + f (n-2) ( Рекурсивното повикване ) .
Междувременно f (0) = 0 и f (1) = 1 ( условие за спиране) .
Тогава наистина е очевидно за нас да дефинираме рекурсивен метод за решаване на проблема:
public int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); }3.3. Преобразуване от десетично в двоично
Сега, нека разгледаме проблема с преобразуването на десетично число в двоично. Изискването е да се приложи метод, който получава положителна цяла стойност n и връща двоично представяне на String .
Един подход за преобразуване на десетично число в двоично е да се раздели стойността на 2, да се запише остатъкът и да се продължи да се разделя коефициентът на 2.
Продължаваме да делим така, докато не получим коефициент 0 . След това, като изписваме всички остатъци в резервен ред, получаваме двоичния низ.
Следователно, нашият проблем е да напишем метод, който връща тези остатъци в резервен ред:
public String toBinary(int n) { if (n <= 1 ) { return String.valueOf(n); } return toBinary(n / 2) + String.valueOf(n % 2); }3.4. Височина на двоично дърво
Височината на двоично дърво се определя като броя на ръбовете от корена до най-дълбокия лист. Нашият проблем сега е да изчислим тази стойност за дадено двоично дърво.
Един прост подход би бил да се намери най-дълбокият лист, след което да се преброят ръбовете между корена и този лист.
Но опитвайки се да мислим за рекурсивно решение, можем да повторим дефиницията за височината на двоично дърво като максималната височина на левия клон на корен и десния клон плюс 1 .
Ако коренът няма ляв клон и десен клон, височината му е нула .
Ето нашето изпълнение:
public int calculateTreeHeight(BinaryNode root){ if (root!= null) { if (root.getLeft() != null || root.getRight() != null) { return 1 + max(calculateTreeHeight(root.left), calculateTreeHeight(root.right)); } } return 0; }Следователно виждаме, че някои проблеми могат да бъдат решени с рекурсия по наистина прост начин.
4. Заключение
В този урок въведохме концепцията за рекурсия в Java и я демонстрирахме с няколко прости примера.
Изпълнението на тази статия може да бъде намерено в Github.