Рекурсия
Язык Java поддерживает рекурсию. Рекурсия в программировании — это когда метод вызывает сам себя. В таком случае метод называют рекурсивным.
Классический пример использования рекурсии, который показывают во всех учебниках по программированию — вычисление факториала числа. Факториал числа N — это произведение всех целых чисел от 1 до N. Например, возьмём число 3 и вычислим его факториал. У нас получится 1 * 2 * 3 = 6. Теперь напишем метод на Java в отдельном классе:
class Factorial < // рекурсивный метод int fact(int n) < int result; if (n == 1) return 1; result = fact(n - 1) * n; return result; >>
Вызовем рекурсивный метод:
Factorial f = new Factorial(); // получим число, введенное пользователем int usernumber = Integer.valueOf(editResult.getText().toString()); // вычисляем факториал и выводим результат в текстовой метке textViewInfo.setText("Факториал " + usernumber + " равен " + f.fact(usernumber));
Теперь, если вводить числа в текстовом поле, то получим следующие результаты:
Факториал 3 равен 6 Факториал 4 равен 24 Факториал 5 равен 120 и т.д.
Понять, как работает метод, довольно трудно, можно всю голову сломать. Однако попробуем. При вызове метода fact() с аргументом, равным 1, вернётся 1. Тут пока понятно. При других числах возвращается fact(n — 1) * n. Получается, что нужно ещё раз вызвать метод fact(). И так происходит до тех пор, пока не дойдёт до единицы. При этом промежуточные значения умножаются.
Когда метод вызывает сам себя, новым локальным переменным и параметром выделяется место в стеке и код метода выполняется с этими новыми начальными значениями. При каждом возврате из рекурсивного вызова старые локальные переменные и параметры удаляются из стека, и выполнение продолжается с момента вызова внутри метода.
Следует помнить, что рекурсивные методы требуют больше ресурсов для выполнения и даже может вызвать переполнение памяти при слишком больших значениях.
Рекурсивные методы часто используют в сортировке, а также в алгоритмах, связанных с искусственным интеллектом. В обычной практике рекурсия используется редко.
При использовании рекурсивных методов нужно смотреть, чтобы в программе был оператор if для выхода из рекурсивного метода без выполнения рекурсивного вызова. Иначе метод никогда не выполнит возврат.
Рассмотрим ещё один пример вывода первых элементов массива. Создадим отдельный класс с рекурсивным методом:
class Recursion < int aValues[]; StringBuilder sb = new StringBuilder(); // Конструктор Recursion(int i) < aValues = new int[i]; >// Рекурсивное отображение элементов массива String printArray(int i) < if (i == 0) return ""; // не забываем про выход из метода else printArray(i - 1); String output = "[" + (i - 1) + "] " + aValues[i - 1] + "\n"; sb.append(output); return sb.toString(); >> public void onClick(View v)
Запустив код мы увидим:
[0] 0 [1] 1 [2] 2 [3] 3 [4] 4
Рекурсия
В Java поддерживается рекурсия. Рекурсия — это процесс определения чего-либо в терминах самого себя. Применительно к программированию на Java рекурсия — это атрибут, который позволяет методу вызывать самого себя. Такой метод называют рекурсивным.
Классический пример рекурсии — вычисление факториала числа. Факториал числа N — это произведение всех целых чисел от 1 до N. Например, факториал 3 равен 1x2x3, или 6. Вот как можно вычислить факториал, используя рекурсивный метод:
// Простой пример рекурсии.
class Factorial // это рекурсивный метод
int fact(int n) int result;
if(n==l) return 1;
result = fact(n-l) * n;
return result;
class Recursion public static void main(String args [ ]) Factorial f = new Factorial ();
System.out.println(«Факториал 3 равен » + f.fact(3));
System.out.println(«Факториал 4 равен » + f.fact(4));
System.out.println(«Факториал 5 равен «.+ f.fact(5));
>
>
Вывод этой программы имеет вид:
Факториал 3 равен 6
Факториал 4 равен 24
Факториал 5 равен 120
Для тех, кто не знаком с рекурсивными методами, работа метода fact () может быть не совсем понятна. Вот как работает этот метод. При вызове метода fact () с аргументом, равным 1, функция возвращает 1. В противном случае она возвращает произведение fact (n-1) *п. Для вычисления этого выражения программа вызывает метод fact () с аргументом 2. Это приведет к третьему вызову метода с аргументом, равным 1. Затем этот вызов возвратит значение 1, которое будет умножено на 2 (значение п во втором вызове метода). Этот результат (равный 2) возвращается исходному вызову метода fact () и умножается на 3 (исходное значение п). В результате мы получаем ответ, равный 6. В метод fact () можно было бы вставить операторы println (), которые будут отображать уровень каждого вызова и промежуточные результаты.
Когда метод вызывает самого себя, новым локальным переменным и параметрам выделяется место в стеке и код метода выполняется с этими новыми начальными значениями. При каждом возврате из рекурсивного вызова старые локальные переменные и параметры удаляются из стека, и выполнение продолжается с момента вызова внутри метода. Рекурсивные методы выполняют действия, подобные выдвиганию и складыванию телескопа.
Из-за дополнительной перегрузки ресурсов, связанной с дополнительными вызовами функций, рекурсивные версии многих подпрограмм могут выполняться несколько медленнее их итерационных аналогов. Большое количество обращений к методу могут вызвать переполнение стека. Поскольку параметры и локальные переменные сохраняются в стеке, а каждый новый вызов создает новые копии этих значений, это может привести к переполнению стека. В этом случае система времени выполнения Java будет генерировать исключение. Однако, вероятно, об этом можно не беспокоиться, если только рекурсивная подпрограмма не начинает себя вести странным образом.
Основное преимущество применения рекурсивных методов состоит в том, что их можно использовать для создания более понятных и простых версий некоторых алгоритмов, чем при использовании итерационных аналогов. Например, алгоритм быстрой сортировки достаточно трудно реализовать итерационным методом. А некоторые типы алгоритмов, связанных с искусственным интеллектом, легче всего реализовать именно с помощью рекурсивных решений.
При использовании рекурсивных методов нужно позаботиться о том, чтобы где-либо в программе присутствовал оператор if, осуществляющий возврат из рекурсивного метода без выполнения рекурсивного вызова. В противном случае, будучи вызванным, метод никогда не выполнит возврат. Эта ошибка очень часто встречается при работе с рекурсией. Поэтому во время разработки советуем как можно чаще использовать операторы println (), чтобы можно было следить за происходящим и прервать выполнение в случае ошибки.
Рассмотрим еще один пример рекурсии. Рекурсивный метод printArray () выводит первые i элементов массива values.
// Еще один пример рекурсии.
class RecTest int values[];
RecTest(int i) values = new int[i];
>
// рекурсивное отображение элементов массива
void printArray(int i) if(i==0) return;
else printArray(i-1);
System.out.println (» [» + (i-1) + «] » + values[i-1]);
>
>
class Recursion2 public static void main(String args[]) RecTest ob = new RecTest(10);
int i;
for(i=0; i
Эта программа генерирует следующий вывод:
Рекурсия в программировании и как ее применять
Что такое “бизнес логика”? И как начать ее понимать
Что такое сигнатура в программировании: терминология и примеры
Что такое консоль в программировании, отличие от командной строки
Что такое компиляция, линковка, run time?
Что такое framework? Объяснение для новичков
Рекурсия — это повторение шаблона с небольшими изменениями. Вокруг нас множество примеров рекурсии, начиная с окон готического собора, заканчивая соцветием капусты. Но нас интересует, что такое рекурсия в программировании, когда ее надо применять, и какие у нее недостатки.
Определение рекурсии в программировании
Рекурсия — это метод программирования, который позволяет функции многократно вызывать себя до тех пор, пока не будет выполнено условие завершения. Условие завершения заставит функцию вернуть значение или выполнить какое-либо действие, либо вызвать переполнение стека и сбой программы.
Виды рекурсии
Существует несколько типов рекурсии, которые можно использовать в программировании:
- Хвостовая рекурсия. Это форма рекурсии, при которой рекурсивный вызов является последней операцией в функции перед ее возвратом.
- Взаимная рекурсия. Это форма рекурсии, при которой две или более функции вызывают друг друга по очереди. Это можно использовать для алгоритмов поиска пути и им подобных.
- Бесконечная рекурсия. Это форма рекурсии, при которой функция бесконечно вызывает сама себя, не достигая условия завершения.
- Рекурсивные структуры данных. Это форма рекурсии, при которой структура данных, например, дерево или список, обращаются к себе самим.
- Мемоизация. Это рекурсивный метод, при котором кешируются прошлые результаты и их возврат вместо повторного вычисления.
Зачем нужна рекурсия в программировании
Рекурсия позволяет программистам разбивать сложные проблемы на подзадачи, а затем решать их с использованием одной и той же техники. Это позволяет избежать использования сложных структур управления, таких как циклы, и вместо этого применять чистый модульный подход.
Рекурсия также позволяет программистам реализовывать сложные алгоритмы, требующие повторяющихся операций, таких как бинарные деревья поиска или последовательности Фибоначчи.
Пример рекурсии в программировании
Примером рекурсивного алгоритма в программировании может быть ряд Фибоначчи, представляющий собой последовательность чисел, где каждое число является суммой двух предыдущих чисел. Формула для этой последовательности: F(n) = F(n-1) + F(n-2), а первые два числа в последовательности равны 0 и 1. Рекурсивный алгоритм для вычисления n-го числа в последовательности Фибоначчи. может выглядеть так в Python:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(5)) # Output: 13
В этом примере функция Фибоначчи принимает в качестве параметра целое число n, которое является n-м числом в последовательности. Функция сначала проверяет базовые случаи, где n = 0 или n = 1. Если n меньше или равно 0, она возвращает 0, а если n равно 1, она возвращает 1. Если n больше 1, функция рекурсивно вызывает себя с параметрами n-1 и n-2, а затем возвращает сумму двух результатов. Рекурсивные вызовы функций вложены друг в друга до тех пор, пока не будет выполнено условие завершения.
Базовый случай и рекурсивный случай
Базовый случай — это когда проблема или условие достаточно просты, чтобы их можно было решить без рекурсии.
Рекурсивный случай — проблема или условие требуют, чтобы функция вызывала себя с другим набором аргументов или входных данных. Рекурсивный случай повторяется до тех пор, пока не будет достигнут базовый случай.
Идея рекурсии состоит в том, чтобы разбить сложную проблему на более простые, пока не будет достигнут базовый случай. Как только базовый случай решен, результат передается обратно по дереву рекурсии как решение исходной проблемы.
Стек вызовов
Стек вызовов, также известный как стек выполнения или просто стек, — это структура данных, в которой хранится информация о вызовах подпрограмм в компьютерной программе. Всякий раз, когда вызывается функция или метод, контекст вызова помещается в стек.
Когда функция или метод выполнены, контекст вызова извлекается из стека, восстанавливаясь до состояния, в котором он находился до вызова функции или метода. Этот процесс известен как раскручивание стека.
Преимущества и недостатки рекурсии
У этого метода есть свои плюсы и минусы. Разберем их далее.
Преимущества рекурсии
- Краткость и понятность кода.
- Высокая производительность на рекурсивных задачах.
- Эффективность использования памяти.
- Функциональное программирование с помощью рекурсий.
- Простота использования.
Недостатки рекурсии
- Возможность переполнения стека.
- Низкая производительность на многоуровневых задачах.
- Более сложная реализация.
- Неуниверсальность применения.
- Подходит не для всех языков программирования.
- Подходит не для всех сред из-за возможных проблем с памятью.
Когда стоит использовать рекурсию, а когда не стоит
Когда использовать рекурсию:
- Рекурсия — хороший выбор, когда проблему можно разбить на более мелкие подзадачи, которые можно решить одним и тем же методом.
- Рекурсия часто используется в функциональном программировании, так как позволяет компоновать и комбинировать функции.
Когда не надо использовать рекурсию:
- Если размер стека ограничен или рекурсия может быть слишком глубокой.
- Если разработчик недостаточно опытен для создания многоуровневой рекурсии.
- Если язык разработки ограничен в поддержке рекурсии.
- Если в задаче предполагается обработка больших массивов данных.
Рекурсия в различных языках программирования
Рекурсия — это понятие, существующее в большинстве языков программирования, и каждый из них имеет свою специфику и возможности. Некоторые из языков, поддерживающих рекурсию, — это Java, Python, JavaScript, C#, PHP, Ruby, Rust, Clojure и другие. В этих языках функции могут вызывать сами себя и рекурсивно решать проблемы.
Рекурсия в языке Python
В языке Python рекурсия используется с помощью функций, которые имеют рекурсивные вызовы, здесь используются генераторы, методы и классы. Кроме того, Python может использовать универсальные типы, подходящие для рекурсивных вызовов, такие как список, кортеж, диапазон.
Самый распространенный способ использования рекурсии в Python — это использование функций, которые рекурсивно вызывают сами себя. Например, функция, которая должна вычислять факториал чисел, принимает один параметр (число). Функция вызывается рекурсивно до тех пор, пока не будет достигнуто число, меньшее или равное 1, после чего она возвращает свой результат.
Рекурсия в языке Java
Рекурсия хорошо поддерживается языком программирования Java и широко в нем распространена. Типичные задачи: реализация обхода дерева, решение задач динамического программирования и реализация методов функционального программирования.
Мы помним, что рекурсия может вызвать переполнение стека. Чтобы избежать этого, используют оптимизацию хвостовой рекурсии, которая позволяет сократить рекурсию до простой итерации, чтобы стек не стал слишком большим.
Рекурсия в языке C++
Рекурсия также поддерживается в языке программирования C++ для решения самых разных задач.
Рекурсию в C++ также можно оптимизировать, чтобы избежать риска переполнения стека и повысить производительность. C++ включает в себя функцию оптимизации хвостового вызова, которая позволяет проводить оптимизацию, аналогичную хвостовой рекурсивной оптимизации Java.
Рекурсия в функциональных языках программирования
В языках функционального программирования рекурсия широко используется как основной строительный блок. Рекурсия лежит в основе многих распространенных методов, таких как отображение, свертывание и развертывание.
В Haskell, одном из самых популярных языков функционального программирования, рекурсия может использоваться для решения самых разных задач, от обработки текста до сетевого анализа и научного моделирования.
Рекурсия широко используется в других языках функционального программирования, включая Lisp, Scheme, Clojure, F#, OCaml, Standard ML и Erlang.
Как прервать рекурсию
В некоторых случаях рекурсия останавливается при достижении базового случая или сценария, при котором функция больше не вызывается. Это позволяет программе завершить работу и вернуть результат.
В других случаях рекурсия останавливается при достижении предела вызовов, установленного языком программирования или системой времени выполнения. Когда этот предел достигнут, рекурсивно вызываемая функция выдает исключение или программа завершается.
Кроме того, рекурсивные функции может останавливать защита, которая проверяет предварительно определенное условие, например достижение определенной глубины рекурсии или обнаружение определенного значения.
В общем, остановка рекурсии важна, чтобы избежать бесконечных циклов и исчерпания ресурсов, таких как память или пространство стека.
Что выбрать: рекурсию или цикл
Использовать рекурсию рекомендуется, когда решаемая проблема естественно рекурсивна по своей природе, например, дерево поиска или вычисление факториала
Цикличные алгоритмы могут быть более эффективными в определенных сценариях, особенно при работе с большими наборами данных. В этих случаях цикл более эффективен и менее требователен к памяти.
В заключение
Многие современные языки программирования поддерживают как рекурсию, так и цикл. Можно переключаться между ними по мере необходимости, чтобы найти наиболее подходящее решение.
Похожие материалы
Что такое “бизнес логика”? И как начать ее понимать
Что такое сигнатура в программировании: терминология и примеры
Что такое консоль в программировании, отличие от командной строки
Что такое компиляция, линковка, run time?
Что такое framework? Объяснение для новичков
Что можно использовать вместо рекурсии?
В некоторых задачах рекурсию можно заменить циклом. Рекурсивный алгоритм может быть заменен итеративным. В некоторых случаях стоит добавить дополнительную структуру данных, как правило, стек.
Почему рекурсивные алгоритмы работают медленнее?
Рекурсивные алгоритмы далеко не всегда работают медленнее цикличных. Обычно это происходит, когда ограничен размер стека или рекурсия очень глубокая. В этом случае стек переполняется, программа начинает тормозить, а затем закрывается с ошибкой.
Как оптимизировать рекурсию в программе?
Во многих средах разработки для разных языков программирования, таких как Java, C++, и других, встроены возможности для TCO — оптимизации хвостовой рекурсии. Можно также провести оптимизацию вручную, но это сложнее и дольше по времени.
Как работает рекурсия в программировании?
Когда функция вызывает саму себя, происходит создание новых экземпляров функции в стеке вызовов. Каждый экземпляр функции имеет свое собственное локальное состояние и выполнение продолжается до достижения базового случая, который останавливает рекурсию. Затем выполнение возвращается к предыдущим экземплярам функции в обратном порядке.
Что такое базовый случай в рекурсии и почему он важен?
Базовый случай в рекурсии — это условие, при котором рекурсивные вызовы прекращаются и рекурсия завершается. Он важен, чтобы предотвратить бесконечную рекурсию и обеспечить завершение функции. Без базового случая рекурсивная функция будет вызываться бесконечное количество раз.
Какая разница между прямой и косвенной рекурсией?
Прямая рекурсия возникает, когда функция вызывает саму себя напрямую. Например, функция для вычисления факториала может вызывать саму себя с аргументом, уменьшенным на 1. Косвенная рекурсия возникает, когда функция A вызывает функцию B, которая, в свою очередь, вызывает функцию A. Такие вызовы образуют замкнутый цикл взаимных вызовов функций.
Что такое рекурсия в java
Отдельно рассмотрим рекурсивные функции. Главное отличие рекурсивных функций от обычных методов состоит в том, что они рекурсивная функция может вызывать саму себя.
Например, рассмотрим функцию, которая вычисляет факториал числа:
static int factorial(int x) < if (x == 1)< return 1; >return x * factorial(x - 1); >
Вначале проверяется условие: если вводимое число не равно 1, то мы умножаем данное число на результат этой же функции, в которую в качестве параметра передается число x-1. То есть происходит рекурсивный спуск. И так дальше, пока не дойдем того момента, когда значение параметра не будет равно единице.
Рекурсивная функция обязательно должна иметь некоторый базовый вариант, который использует оператор return и который помещается в начале функции. В случае с факториалом это if (x == 1) return 1; . И все рекурсивные вызовы должны обращаться к подфункциям, которые в конечном счете сходятся к базовому варианту. Так, при передаче в функцию положительного числа при дальнейших рекурсивных вызовах подфункций в них будет передаваться каждый раз число, меньшее на единицу. И в конце концов мы дойдем до ситуации, когда число будет равно 1, и будет использован базовый вариант.
Хотя в данном случае нужно отметить, что для определения факториала есть более оптимальные решения на основе циклов:
static int factorial(int x) < int result=1; for (int i = 1; i return result; >
Еще одним распространенным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. В теории n-й член последовательности Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1.
static int fibonachi(int n) < if (n == 0)< return 0; >if (n == 1) < return 1; >else < return fibonachi(n - 1) + fibonachi(n - 2); >>