Что такое рекурсия java
Перейти к содержимому

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

  • автор:

Рекурсия

Рекурсия — это средство, которое позволяет методу вызывать самого себя. Такой метод называется рекурсивным.

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

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

В следующем примере показана реализация подсчета факториала с помощью рекурсии на языке Java. Метод factorial() рекурсивно вызывает самого себя. В рекурсивном методе обязательно задавать точку возврата — условие при котором прекращается рекурсивный вызов метода. Если этого не сделать программа зациклится. В методе factorial() — это проверка на 1.

public class Recursion < static int factorial(int n) < int result; if (n < 2) < return 1; >result = factorial(n - 1) * n; return result; > public static void main(String[] args) < System.out.println("Факториал 3: " + factorial(3)); System.out.println("Факториал 4: " + factorial(4)); System.out.println("Факториал 5: " + factorial(5)); >>
  • Процедурное и объектно-ориентированное программирование
  • Принципы ООП
  • Классы и объекты
  • Конструктор
  • Ключевое слово this
  • Перегрузка
  • Стек и куча
  • Передача объектов в методы
  • Java varargs
  • Сборщик мусора и метод finalize
  • Наследование
  • Ключевое слово super
  • Модификаторы доступа
  • Геттеры и сеттеры
  • Переопределение методов
  • Абстрактные классы и методы
  • Ключевое слово final
  • Задания

Что такое рекурсия 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); >>

Рекурсия

Рекурсия в реальном мире — зеркальный коридор, уходящий в бесконечность:

Рекурсия в программировании — это когда метод вызывает самого себя. Такой метод называют рекурсивным. Но прежде, чем говорить о рекурсии, рассмотрим как происходит вызов того или иного метода. С методом, как мы уже успели увидеть, связано две важные операции:

  1. Объявление — определение метода с именем и параметрами;
  2. Вызов — применение метода к некоторым данным.

Каждый раз, при использовании рекурсии, задействуется стек (stack) вызовов. Stack – это отдельный участок памяти, в котором хранятся инструкции о возврате результатов вызванных методов. Используется метод: кто пришел последний — уйдет первым (LIFO). Stack также представляет собой специальную коллекция, у которой есть методы:

  • Push, т.е. «добавить (втолкнуть) элемент»;
  • Pop «взять(достать/забрать/вытолкнуть) элемент».

Допустим, определено три метода: A(x), B(x) и С(x) и они вызваны их в main(). Тогда стек будет выглядеть так:

Рекурсивный метод обязательно должен иметь, так называемый, базовый вариант, который использует оператор return и помещается в начале метода. Базовый вариант — условие завершение рекурсивных вызовов.

Рекурсия и факториал

Обычно рекурсию рассматривают на примере вычисления факториала – произведение всех натуральных чисел, начиная от 1 и до N:

Рекурсия и факториал

Факториал: примеры вычислений

Тогда объявление и вызов метода factorial будут выглядеть так:

public class Program < public static void main(String args[]) < System.out.println(factorial(4)); // 24 >static int factorial(int x) < if (x == 1) < // базовый return 1; // вариант >return x * factorial(x - 1); // рекурсивный вызов > > 

Рассмотрим работу кода выше наглядно, для factorial(5):

Рекурсия - наглядно

Рекурсия и числа Фибоначчи

Нередко, при рассмотрении рекурсии используют и числа Фибоначчи[wiki]. Это последовательность чисел, в которой первые два элемента — 0 и 1, соответственно, а каждый последующий элемент представляет собой сумму двух предыдущий. Выглядит ряд Фибоначчи из 15 значений так:

Рекурсия и Фибоначчи

Соответственно, число Фибоначчи №15 будет — 377. Код метода рекурсивного вычисления числа Фибоначчи по заданному номеру будет выглядеть так:

public class Program < public static void main(String[] args) < System.out.println(fibonacciSeries(15)); // выведет 377 >public static int fibonacciSeries(int num) < if (num else if (num == 2) < // базовый return 1; // вариант №2 >else < // рекурсивный вызов с выходом return fibonacciSeries(num - 1) + fibonacciSeries(num - 2); >> >

Разумеется, и факториал, и числа Фибоначчи, могут быть вычислены и в цикле (методом итерации).

Например, один их вариантов вычисления чисел Фибоначчи с помощью цикла будет выглядеть так:

import java.util.Arrays; public class Program < public static void main(String[] args) < System.out.println(fibonacciSeries(15)); >public static int fibonacciSeries(int num) < int[] arr = new int[num]; // массив чисел arr[0] = 0; // первое число arr[1] = 1; // второе число // заполняем массив последующими числами for (int i = 2; i < arr.length; ++i) < arr[i] = arr[i - 1] + arr[i - 2]; >// Вывод полученного массива для наглядности System.out.println("Fibonacci Series: " + Arrays.toString(arr)); return arr[arr.length - 1]; > >

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

Задача : написать программу вычисления факториала с помощью цикла (методом итераций).

Решение (раскрыть) [Свернуть]:

public class Program < public static void main(String[] args) < System.out.println(factorial(5)); // 120 >public static int factorial(int num) < int factorial = 1; // факториал от 0 // итерации для вычисления for (int i = 1; i return factorial; > >

Рекурсия в Java

Рекурсия в Java - 1

Чтобы понять, что такое рекурсия, нужно понять, что такое рекурсия. На самом деле, в понимании таких функций нет ничего сложного, нужно только один раз хорошо в этом разобраться. И попрактиковаться, если речь идёт о программировании. Рекурсия встречается не только в программировании, но и в реальной жизни. Возьми в руки зеркало и встань напротив другого зеркала. Отражение отражения отразится в отражении и так далее. Ты увидишь бесконечное количество отражений, уходящих в бесконечность. Больше о “реальной” рекурсии ты можешь найти в статье “Дню Сурка посвящается…” Возвратимся из реального мира к будням программиста. Простое определение: рекурсивные функции в java – это функции, которые вызывают сами себя. Приведу очень простой и очень вредный пример:

 public void recursionFucn()
  • Базис рекурсии – условие выхода из блока рекурсивных вызовов – базисное решение задачи, при условиях, когда нет необходимости вызывать рекурсию.
  • Шаг рекурсии – вызов функцией самой себя при изменении параметров.

Java-университет

Классический пример применения рекурсивной функции – вычисление факториала от числа. Если вдруг забыл, напомню: факториал положительного целого числа N (обозначается как N!) — это произведение чисел от 1 до N: N! = 1 * 2 * 3 * … (N — 1) * N . Кстати, факториал нуля по определению равен 1. Так что факториал можно найти для любого целого положительного числа и нуля (на языке математики — для множества неотрицательных целых чисел или же для множества натуральных чисел и нуля). Думаю, ты понимаешь, что запрограммировать факториал можно с помощью циклов. Собственно, вот нерекурсивный метод решения этой задачи:

 private int fact(int n) < int result = 1; for (int i = 1; i return result; > 

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

 private int fact(int n) < if (n < 0) < System.out.println("Зачем тебе факториал из отрицательного числа?"); return null; >int result = 1; if (n == 0) < return result; >for (int i = 1; i return result; > 

Теперь приведу код метода для рекурсивного решения этой задачи:

 private int factorial(int n) < int result = 1; if (n == 1 || n == 0) < return result; >result = n * factorial(n-1); return result; > 

Посмотрим результаты вывода для вызовов:

 System.out.println(factorial(0)); System.out.println(factorial(1)); System.out.println(factorial(2)); System.out.println(factorial(3)); System.out.println(factorial(4)); System.out.println(factorial(5)); System.out.println(factorial(6)); 

Получим ожидаемые значения:

 1 1 2 6 24 120 720 

Добавим красивый вывод и вычислим фаториал для числа побольше:

 private int factorial(int n) < int result = 1; if (n == 0) < System.out.print(" = "); return result; >if (n == 1) < System.out.print(" * 1 = "); return result; >System.out.print(n); if (n != 2) < System.out.print(" * "); >result = n * factorial(n-1); return result; > System.out.println(factorial(15) + "!"); 

Получим: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! В данном случае применение рекурсивной функции оправдано и безопасно. Мы четко обозначили условие выхода из рекурсивного блока, и мы уверены в том, что он достижим: мы вводим целое неотрицательное число, в случае, если число равно нулю или единице — возвращаем результат, если же число больше — умножаем результат на функцию от числа n-1 . На примере факториала от трех:

 factorial(3) внутри себя выполнит следующее: result = 3 * factorial(2); (рекурсивный вызов) factorial(2) внутри себя выполнит следующее: result = 2 * factorial(1); (рекурсивный вызов) factorial(1) вернет 1 (базис рекурсии) factorial(2) вернет 2 * 1 factorial(3) вернет 3 * 2 * 1 

По поводу осторожности применения: в чем уязвимость этой функции? Если дать методу в качестве параметра отрицательное число, то проверка

 if (n == 1 || n == 0)

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

 if (n

И все будет хорошо.

В чем преимущество одного метода перед другим? Кажется, что большой разницы нет, но на самом деле множество рекурсивных вызовов негативно скажется на производительности и потребляемой памяти: стек вызовов – практически неконтролируемый ресурс и при разных условиях вызова одной и той же рекурсивной функции, мы можем получить или не получить проблемы, связанные с этим ресурсом. Практически все задачи, решаемые с помощью итераций (циклов типа for-each ), можно решить и рекурсивно. Преимущество рекурсии в читаемости и простоте написания, о недостатках мы говорили выше: возможность «выстрелить себе в ногу» неиллюзорна. Еще более осторожным надо быть при использовании так называемой «сложной рекурсии»: Функция A() вызовет функцию B() , вызывающую функцию A() .Для решения таких задач необходимо полное понимание того, как работает рекурсия. Пример такой задачи: вычисление значения x^n/(n!) . Факториал, как мы обсуждали выше, определен на множестве неотрицательных целых чисел. Напоследок приведу код решения. Сложная рекурсия будет состоять из двух методов:

 private double calculate(int x, int n) < return power(x, n) / n; >private double power(int x, int n)

Для входа в рекурсию используется метод calculate , вызывающий метод power , в свою очередь вызывающий метод calculate . Базис рекурсии мы обозначили в методе power:

 if (n == 1) return x; 

Там же определен и шаг рекурсии:

 return x * calculate(x, n - 1); 
  • Любое число, кроме нуля, в нулевой степени равно 1 . Если n = 0 , то n! = 1 . Нужно вернуть 1 .
  • Нуль в любой степени равен нулю.
  • Неопределенность типа 0^0 рассматривать не будем и примем такие входные данные за невалидные.
 private double calculate(int x, int n) throws ArithmeticException < if (x == 0 && n == 0) < throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0"); >if (n < 0) < throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!"); >if (n == 0) < return 1; >if (x == 0) < return 0; >if (x == 0) < return 0; >return power(x, n) / n; > private double power(int x, int n)

Ну, и при вызове функции нужно не забыть поймать ошибку:

 try < System.out.println(calculate(x, n)); >catch (ArithmeticException e)

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *