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

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

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

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

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

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

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

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

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

НАЧАЛО
ЗАЯВИТЬ сумму, считать как целое число
сумма = 0
count = 1
ПОВТОРИТЬ
Сумма = сумма + счет
Счетчик = Счет + 1
ДО СЧЕТА> n
КОНЕЦ

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

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

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

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

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

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

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

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

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

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

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

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

Function () {
//базовый вариант
// общий случай
}

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

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

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

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

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

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

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

// рекурсивная функция
int Sum (int n) { 
//базовый вариант
if (n <= 1) {
возврат 1;
}
// общий случай
еще{
вернуть 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 (Сумма (7));

Что вы узнали

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

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

Что такое рекурсия и как ее использовать?

Изучите основы рекурсии, важного, но немного умопомрачительного инструмента для программистов.

Читать далее

Об авторе