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

Никогда нельзя недооценивать необходимость повторения кода в поисках решений некоторых из самых больших мировых проблем. Что вам нужно знать, так это то, что в программировании повторение принимает одну из двух форм – итерацию или рекурсию.

Цель здесь – познакомить вас с повторением кода и продемонстрировать, как его можно использовать для улучшения ваших программ Java.

Повторяющиеся программы могут помочь вам решить некоторые из самых сложных проблем программирования. Вот что вам нужно знать для создания рекурсивных программ на Java.

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

Итерация использует структуру цикла для повторения кода. Три типа итерационных структур – это цикл перед тестированием (while), цикл после тестирования (do-while) и цикл с контролем счетчика (for) .

Эти итерационные структуры работают, повторяя блок кода, пока определенное условие остается истинным, но как только это условие становится ложным, цикл останавливается, и программа возвращается к своему нормальному потоку.

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

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

 
START
 DECLEARE sum, count as integer
 sum = 0
 count = 1
 REPEAT
 Sum = sum + count
 Count = count + 1
 UNTIL count > n
 END

В приведенном выше псевдокоде есть две переменные, sum и count, которые инициализируются значениями 0 и 1 соответственно. Переменная count инициализируется значением 1, потому что проблема, которую мы пытаемся решить, утверждает, что нам нужна сумма всех целых чисел от 1 до n.

Переменной «n» будет присвоено случайное число от пользователя, а переменная «count» будет увеличиваться на единицу при каждом выполнении цикла, но как только значение переменной «count» превысит значение «n», тогда цикл остановится.

Зачем использовать рекурсию?

Если бы мы исследовали факты, связанные с итерацией и рекурсией, мы обнаружим, что несколько вещей будут правдой.

• Оба метода предполагают повторение.
• Оба метода требуют условия проверки, которое укажет, когда следует остановиться.
• Оба метода теоретически могут выполняться вечно, если условие выхода не задано или не выполнено.
• Любая проблема, которую можно решить с помощью итерации, также может быть решена с помощью рекурсии и наоборот.

Так почему мы должны предпочесть один метод другому? Простой ответ – эффективность. С помощью рекурсии программист может использовать меньше кода для достижения, по сути, того же результата. Меньше кода означает, что вероятность того, что ошибки останутся незамеченными, значительно снизится.

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

Связанный: Исключения Java: правильно ли вы с ними обращаетесь?

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

Рекурсия – это имя, данное процессу, в котором функция многократно вызывает себя до тех пор, пока не будет выполнено определенное условие. Этот повторяющийся метод решает проблемы, разбивая их на более мелкие и простые версии самих себя.

Каждая рекурсивная функция состоит из двух частей – основного и общего.

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

 
Function(){
 //base case
 //general case
 }

Базовый случай – это часть рекурсивной функции, которая решает проблему. Итак, всякий раз, когда рекурсивная функция достигает базового случая, программа выходит из рекурсивной функции и продолжает свой естественный поток.

Общий случай – это повторяющаяся часть рекурсивной функции. Здесь функция вызывает сама себя и здесь выполняется основная часть работы.

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

Некоторые языки программирования поддерживают только итерацию, в то время как другие поддерживают только рекурсию. К счастью, Java – один из языков, поддерживающих оба повторяющихся метода.

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

Вернемся к нашему первоначальному примеру суммирования, цель состоит в том, чтобы найти сумму всех целых чисел от 1 до n, где n – целое число, предоставленное пользователем.

Пример рекурсии Java

 
//recursive function
 int Sum(int n){
 //base case
 if (n <= 1){
 return 1;
 }
 //general case
 else{
 return n + Sum(n-1);
 }
 }

Рекурсивная функция выше принимает целое число «n» и завершает свое выполнение только тогда, когда значение n меньше или равно 1.

Если бы мы передали целое число 5 в программу выше, переменная «n» приняла бы значение 5. Тогда значение «n» было бы проверено в базовом случае, но с учетом того, что 5 больше, чем 1 «n. Теперь перейдем к общему случаю.

В этом примере общий случай вызовет рекурсивную функцию четыре раза. При последнем вызове функции значение «n» будет равно 1, что фактически соответствует требованиям базового случая, что приводит к завершению рекурсивной функции и возврату 15.

Если мы изменим значение «n» на 7, рекурсивная функция вызовет себя шесть раз и вернет 28 перед завершением своего выполнения.

Хотите попробовать на себе? Вы можете выполнить указанную выше рекурсивную программу, используя следующую строку кода в функции main вашей программы Java.

 
System.out.println( Sum(7));

Что вы узнали

Если вы прочитали всю эту статью, то теперь у вас есть базовое представление о двух повторяющихся методах, которые используются в программировании. Теперь вы понимаете сходство между итерацией и рекурсией, и почему разработчик предпочел бы использовать рекурсию вместо итерации, и как использовать рекурсивную функцию в Java.

Кредит изображения: ThisIsEngineering / Pexels