Что такое рекурсия java

Рекурсия

Язык 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 поддерживается рекурсия — процесс определения чего-либо отно­сительно самого себя.

Применительно к программированию на 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 ; class Recursion < public static void main ( String args [ ] ) < Factorial fact = new Factorial ( ) ; System . out . println ( "Факториал 5 равен " + fact . fact ( 5 ) ) ; System . out . println ( "Факториал 10 равен " + fact . fact ( 10 ) ) ; System . out . println ( "Факториал 12 равен " + fact . fact ( 12 ) ) ; System . out . println ( "Факториал 15 равен " + fact . fact ( 15 ) ) ;

Ниже приведен результат, выводимый этой программой.

pro — java . ru @admin : ~ $ javac recursion . java
pro — java . ru @admin : ~ $ java Recursion
Факториал 5 равен 120
Факториал 10 равен 3628800
Факториал 12 равен 479001600
Факториал 15 равен 2004310016
pro — java . ru @admin : ~ $

Тем, кто незнаком с рекурсивными методами, принцип действия метода fact() может быть не совсем понятным.

Метод fact() действует следующим образом. Когда этот метод вызывается со значением 1 своего аргумента, возвращается зна­чение 1. В противном случае возвращается произведение fact(n — 1) * n .

Для вычисления этого выражения метод fact() вызывается со значением n — 1 своего аргумента. Этот процесс повторяется до тех пор, пока n не станет равным 1, после чего начнется возврат из последовательных вызовов метода fact().

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

Для расчета факториала числа З вслед за пер­вым вызовом метода fact() происходит второй вызов этого метода со значением 2 его аргумента.

Это, в свою очередь, приводит к третьему вызову метода fact() со значением 1 его аргумента. Возвращаемое из этого вызова значение 1 затем ум­ножается на 2 (т.е. значение n при втором вызове метода).

Полученный результат ,равный 2 , возвращается далее исходному вызову метода fact() и умножается на 3 (исходное значение n).

В конечном итоге получается искомый результат, равный 6. В метод fact() можно было бы ввести вызовы метода println(), чтобы отобра­жать уровень каждого вызова и промежуточные результаты вычисления фактори­ала заданного числа.

Когда рекурсивный метод вызывает самого себя, новым локальным переменными параметрам выделяется место в стеке и код метода выполняется с этими новы­ми исходными значениями.

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

Рекурсивные методы выполняют дей­ствия, которые можно сравнить с раскладыванием и складыванием телескопа.

Вследствие издержек на дополнительные вызовы рекурсивные варианты мно­гих процедур могут выполняться медленнее их итерационных аналогов.

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

В таком случаев исполняющей системе Jаvа возникнет исключение. Но подобная ситуация не воз­никнет, если не выпустить рекурсивный метод из-под контроля.

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

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

При написании рекурсивных методов следует позаботиться о том, чтобы в каком ­нибудь другом месте программы присутствовал условный оператор if, осуществляю­щий возврат из метода без его рекурсивного вызова.

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

Поэтому на стадии разработки рекурсивных методов рекомендуется как можно чаще делать вызовы метода println(), чтобы сле­дить за происходящим и прерывать выполнение при обнаружении ошибки.

Рассмотрим еще один пример организации рекурсии. В данном примере рекур­сивный метод рrintArrау() выводит первые i элементов из массива values.

Что такое рекурсия?

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

Что такое рекурсия- основное условие в рекурсии

В рекурсивной программе предлагается решение основного случая, а решение более крупной задачи выражается в условиях меньших задач:

int fact(int n) < if (n < = 1) // основной случай return 1; else return n*fact(n-1); >

Почему ошибка переполнения стека происходит в рекурсии?

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

int fact(int n) < // неправильный основной случай (это может вызвать // переполнение стека). if (n == 100) return 1; else return n*fact(n-1); >

Если вызывается рекурсивная функция C fact (10) , она будет вызывать fact (9) , fact (8) , fact (7) и т. д. Но переменная никогда не достигнет значения 100 . Таким образом, конечный вариант не достигается. Если память исчерпана функциями в стеке, это вызовет ошибку переполнения стека.

В чем разница между прямой и косвенной рекурсиями?

Функция fun называется прямой рекурсивной, если она вызывает ту же функцию fun . Функция fun называется косвенной рекурсивной, если она вызывает другую функцию. Разница между прямой и косвенной рекурсией проиллюстрирована в коде ниже:

// Пример прямой рекурсии void directRecFun() < // Какой-то код. directRecFun(); // Какой-то код. >// Пример косвенной рекурсии void indirectRecFun1() < // Some code. indirectRecFun2(); // Some code. >void indirectRecFun2() < // Какой-то код. indirectRecFun1(); // Какой-то код. >

В чем разница между хвостовой и не хвостовой рекурсиями?

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

Как распределена память для разных вызовов функций в рекурсии?

Когда функция вызывается из main() , ей выделяется память в стеке. Рекурсивная функция вызывает себя. Память для вызываемой функции выделяется поверх памяти, выделенной для функции вызова. Для каждого вызова функции создается отдельная копия локальных переменных. Когда конечный вариант достигнут, функция возвращает свое значение функции, которой она вызвана, память освобождается, и процесс продолжается.

Приведем пример, когда рекурсия работает, выполняя простую функцию:

// в программе на C++ показывается работа // рекурсии #include using namespace std; void printFun(int test) < if (test < 1) return; else < cout > int main()

Когда printFun(3) вызывается из main() , память присваивается printFun(3) , а локальная переменная test инициализируется значением 3 . При этом выражения 1 — 4 помещаются в стек, как показано на диаграмме, представленной ниже. Сначала выводится « 3 ». Во втором выражении вызывается printFun(2) и память присваивается printFun(2) , а локальная переменная test инициализируется значением 2 , а выражения 1 — 4 помещаются в стек. Аналогично, printFun(2) вызывает printFun(1) и printFun(1) вызывает printFun(0) . printFun(0) переходит в fact if , и возвращается к printFun(1) . Остальные выражения printFun(1) выполняются и возвращаются к printFun(2) и так далее. Выводятся значения от 3 до 1 , а затем печатаются от 1 до 3 . Стек памяти рекурсивной функции показан на диаграмме, приведенной ниже:

Каковы недостатки рекурсивного программирования по сравнению с итеративным программированием?

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

Рекурсия также занимает больше времени из-за вызовов функций и издержек на возврат.

Каковы преимущества рекурсивного программирования над итерационным программированием?

Рекурсия обеспечивает простой и понятный способ написания кода. Некоторые задачи являются неотъемлемо рекурсивными. Для них предпочтительнее использовать рекурсивный код. Подобный код можно писать итеративно с помощью структуры данных « стек ».

Java. Рекурсия. Примеры решения задач. Преимущества и недостатки рекурсии

Рекурсия. Примеры решения задач. Преимущества и недостатки рекурсии

Поиск на других ресурсах:

1. Что такое рекурсия? Что называется рекурсией?

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

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

2. Объяснение к реализации задач на рекурсию. Как правильно организовать рекурсивный вызов функции?

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

Чтобы циклический процесс превратить в рекурсивный, нужно уметь определить (выделить) три важных момента:

• условие прекращения рекурсивного процесса. Например, если счетчик или итератор с именем k изменяется от 1 до 10 в возрастающем порядке, то условие прекращения есть достижение значения k =10. Условие прекращения указывается в операторе return ;
• формулу следующего элемента или итератора, который используется в рекурсивном процессе. Эта формула указывается в операторе return ;
• перечень параметров, которые передаются в рекурсивную функцию. Один из параметров обязательно есть итератор (счетчик), изменяющий свое значение. Другие параметры являются дополнительными, например, ссылка на обрабатываемый массив.

3. Поиск суммы элементов массива. Пример

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

Задача. Задан массив чисел A . Разработать рекурсивную функцию, которая находит сумму элементов массива:

где n – количество элементов массива. Программный код функции следующий:

// рекурсия - сумма элементов массива static int Sum(int i, int[] A) <  if (i==(A.length-1))  return A[i];  return A[i] + Sum(i+1,A); >

В вышеприведенном коде функция получает два параметра. Первый параметр i есть значением текущего индекса, который изменяет свое значение при каждом рекурсивном вызове. Второй параметр A – массив, элементы которого суммируются.

Последний элемент массива имеет индекс A.length-1 . Достижение функцией последнего элемента массива есть выходом из нее. Поэтому, в тексте функции Sum() указывается условие прекращения рекурсивного процесса:

if (i==(A.length-1))  return A[i];

В языке Java массив есть экземпляром (объектом) класса, поэтому количество элементов в массиве определяется свойством length . Это есть удобным, поскольку не нужно передавать размерность массива в виде параметра (в отличие от некоторых других языков программирования).

Поскольку, осуществляется сумма текущего значения A[i] со следующими, то указывается строка

// A[i] - текущее значение, Sum(i+1,A) – следующее значение в массиве return A[i] + Sum(i+1,A);

где Sum(i+1, A) означает следующее значение массива A , которое будет вычислено на следующем (нижнем) уровне рекурсивного вызова. Параметр i+1 указывает, что на следующем уровне рекурсии будут взяты следующий за данным элемент массива.

Использование функции Sum() в другом программном коде может быть следующим:

int[] A = < 3, 12, 10, 11 >; int sum; sum = Sum(0,A); // sum = 36

4. Вычисление факториала числа – n! . Пример

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

Программный код функции следующий:

// вычисление факториала числа n int Fact(int n) <  if (n==1)  return 1; // условие завершения рекурсивного процесса  else  return n*Fact(n-1); // Fact(n-1) - результат следующих вызовов функции >

В данной функции происходит рекурсивный вызов функции Fact() с параметром n , который изменяется от n до 1 в порядке убывания. Рекурсивный процесс завершается при n = 1.

При возврате на уровень выше возвращается текущее значение n и результат вычислений при следующих рекурсивных вызовах:

return n*Fact(n-1);

Использование функции в другом программном коде:

int fact; fact = Fact(7); // fact = 5040

5. Программа нахождения наибольшего общего делителя по алгоритму Евклида. Пример

В примере определяется наибольший общий делитель по формуле Евклида:

Программный код функции следующий:

// НОД - Алгоритм Евклида int MaxDivisor(int n, int m) <  if (n==m) return n;  else  if (n>m) return MaxDivisor(n-m, m);  else  return MaxDivisor(n, m-n); // n >

Использование функции MaxDivisor

int md; md = MaxDivisor(28,20); // md = 4

6. Вычислить n -й член последовательности чисел Фибоначчи. Пример

Последовательность чисел Фибоначчи имеет вид:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

В последовательности чисел Фибоначчи каждое следующее число n определяется как сумма двух предшествующих чисел: (n-1) + (n-2) . Поэтому, в формуле рекурсивного процесса может быть вызов суммы двух функций а не одной. Прекращение рекурсивного процесса достигается, если значение n =0.

Ниже приведен текст функции GetNFibonacci()

// Определение n-го числа Фибоначчи static int GetNFibonacci(int n) <  if (n>1)  return GetNFibonacci(n-2)+GetNFibonacci(n-1); // формула Фибоначчи  else  if (n==1)  return 1;  else  return 0; // если n==0 >

Использование метода GetNFibonacci() в другом программном коде:

int n; n = GetNFibonacci(10); // n = 55

7. Преимущества и недостатки использования рекурсии

Рекурсию часто сравнивают с итерацией. Организация циклического процесса с помощью рекурсии имеет свои преимущества и недостатки.

Можно выделить следующие взаимосвязанные преимущества рекурсии:

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

Недостатки рекурсии состоят в следующем:

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

Связанные темы