Какво е рекурсивна функция и как да я създадете в Java?

Необходимостта от повторение на кода никога не може да бъде подценявана в търсенето на решения на някои от най-големите проблеми в света. Това, което трябва да знаете, е, че при програмирането повторението приема една от двете форми - итерация или рекурсия.

Целта тук е да ви запозная с повторението в кода и да демонстрирам как може да се използва за подобряване на вашите Java програми.

Повтарящите се програми могат да ви помогнат да решите някои от най-трудните проблеми с програмирането. Ето какво трябва да знаете, за да създавате рекурсивни програми в Java.

Използване на итерация

Итерацията използва циклична структура за повторение на кода. Трите типа итеративни структури са цикъл преди тест (while), цикъл след тест (do-while) и контра-контролиран контур (за).

Тези итеративни структури работят чрез повтаряне на блок от код, докато остава специфично условие true, но щом това условие стане фалшиво, цикълът спира и програмата се връща към нормалното си състояние поток.

Например, бихме могли да използваме една от итеративните структури, за да решим проблема със сумата на всички цели числа от 1 до n. В зависимост от използваната итеративна структура, решението ще приеме конкретна форма, но всяка от трите итеративни структури могат да осигурят решение на този проблем, като използват следното псевдокод.

Пример за псевдокод на итерация

СТАРТ
DECLEARE сума, брои се като цяло число
сума = 0
брой = 1
ПОВТОРЕТЕ
Сума = сума + брой
Брой = брой + 1
ДО Брой> n
КРАЙ

Горният псевдокод има две променливи, сума и брой, които се инициализират съответно на 0 и 1. Променливата "count" се инициализира на 1, защото проблемът, който се опитваме да разрешим, гласи, че се нуждаем от сумата на всички цели числа от 1 до n.

Променливата „n“ ще бъде присвоена на произволно число от потребителя и променливата „count“ ще се увеличи с по една време цикълът се изпълнява, но веднага щом стойността на променливата "count" надвиши тази на "n", тогава цикълът ще Спри се.

Защо да използвам рекурсия?

Ако трябваше да изследваме фактите около итерацията и рекурсията, ще открием, че няколко неща са верни.

• И двата метода включват повторение.
• И двата метода изискват условие за тест, което ще посочи кога да спре.
• И двата метода могат теоретично да се изпълняват завинаги, ако условието за изход не е дадено или изпълнено.
• Всеки проблем, който може да бъде решен с помощта на итерация, също може да бъде решен с помощта на рекурсия и обратно.

И така, защо бихме искали да изберем единия метод пред другия? Простият отговор е ефективността. С рекурсия програмистът може да използва по-малко код, за да постигне това, което по същество е един и същ резултат. По-малко код означава, че има значително намаляване на възможността грешките да останат незабелязани.

Рекурсията използва повече памет и е по-бавна от итерацията, но има вграден стек (структура на данните). С итерация ще трябва да изградите структура на данни (по същество да преоткриете колелото), оставяйки програмата си отворена за по-голяма възможност за неразкрити грешки поради допълнителния код.

Свързани: Изключения на Java: Справяте ли се правилно с тях?

Как работи рекурсията

Рекурсията е името, дадено на процес, при който функция многократно се самоизвиква, докато не бъде изпълнено конкретно условие. Този повтарящ се метод решава проблемите, като ги разделя на по-малки, по-опростени версии на себе си.

Всяка рекурсивна функция се състои от две части - основен случай и общ случай.

Основна структура на пример за рекурсивна функция

Функция () {
// основен случай
// общ случай
}

Основният случай е секцията на рекурсивната функция, която решава проблема. Така че, когато рекурсивната функция пристигне в основния случай, програмата излиза от рекурсивната функция и продължава с естествения си поток.

Общият случай е раздела на рекурсивната функция, който се повтаря. Това е мястото, където функцията се извиква и където се извършва основната част от работата.

Използване на рекурсия в Java

Някои езици за програмиране поддържат само итерация, докато други поддържат само рекурсия. За щастие Java е един от езиците, които поддържат и двата повтарящи се метода.

В Java рекурсията се използва по същия начин, по който се използва на всеки друг език, който я поддържа. Ключът е винаги да се гарантира, че вашата рекурсивна функция има както основен, така и общ случай, в този ред.

Да се ​​върнем към нашия първоначален пример за сумиране, целта е да се намери сумата на всички цели числа от 1 до n, където n е цяло число, предоставено от потребителя.

Пример за рекурсия на Java

// рекурсивна функция
int Sum (int n) { 
// основен случай
ако (n <= 1) {
връщане 1;
}
// общ случай
друго {
връщане n + Сума (n-1);
}
}

Горната рекурсивна функция приема цяло число „n“ и прекратява изпълнението си само когато стойността на n е по-малка или равна на 1.

Ако трябва да предадем цялото число 5 на програмата по-горе, променливата "n" би приела стойността на 5. След това стойността на „n“ ще бъде проверена в основния случай, но като се има предвид, че 5 е по-голямо от 1 „n“, сега ще бъде предадено на общия случай.

В този пример общият случай ще извика рекурсивната функция четири пъти. При последното извикване на функцията стойността на „n“ ще бъде 1, като ефективно отговаря на изискванията на основния случай, което води до прекратяване на рекурсивната функция и връщане на 15.

Ако променим стойността на „n“ на 7, рекурсивната функция ще се извика шест пъти и ще върне 28, преди да прекрати изпълнението си.

Искате ли да опитате за себе си? Можете да изпълните рекурсивната програма по-горе, като използвате следния ред код в основната функция на вашата Java програма.

System.out.println (Сума (7));

Какво научихте

Ако сте преминали през цялата тази статия, сега имате основно разбиране за двата повтарящи се метода, които се използват при програмирането. Сега разпознавате приликите между итерация и рекурсия и защо разработчикът би избрал да използва рекурсия над итерация и как да използва рекурсивна функция в Java.

Кредит за изображение: ThisIsEngineering /Пексели

Какво представлява рекурсията и как я използвате?

Научете основите на рекурсията, същественият, но леко умопомрачителен инструмент за програмистите.

Прочетете Напред

За автора