Что такое рекурсия 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
  • Задания

Что такое рекурсия, рекурсивный и итеративный процесс в программировании

Что такое рекурсия, рекурсивный и итеративный процесс в программировании главное изображение

Рекурсия vs рекурсивный или итеративный процесс: в чем разница

Рекурсия — это функция, которая вызывает саму себя, но с другими значениями параметров.

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

Теперь давайте поговорим о компьютерах. Для выполнения задач им нужны инструкции. Когда компьютер выполняет набор инструкций — это процесс. Ваш работающий сейчас браузер — тоже процесс. Простой цикл, выводящий на экран десять раз число «42» — также процесс.

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

Бесплатные курсы по программированию в Хекслете

  • Освойте азы современных языков программирования
  • Изучите работу с Git и командной строкой
  • Выберите себе профессию или улучшите навыки

Методы решения задач с помощью рекурсии

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

Давайте продолжим аналогию с музыкальной гармонией и подумаем про фортепиано. При написании музыки используем эту концепцию — «гармонию звуков». Можно придумать разные способы: рассчитывать частоты звуков — ноты — математическими формулами или рассчитывать правильные расстояния между клавишами.

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

В чем отличие рекурсивного процесса от итеративного

Рекурсивный процесс на каждом шаге рекурсии говорит «я это запомню и потом посчитаю». «Потом» наступает в самом конце.

  • Если рекурсивный процесс считает факториал 6, то ему нужно запомнить 5 чисел, чтобы посчитать их в самом конце, когда уже никуда не деться и рекурсивно двигаться вниз больше нельзя
  • Когда мы находимся в очередном вызове функции, то где-то снаружи этого вызова в памяти хранятся эти запомненные числа

На этой картинке видно, как растет использование памяти: процессу нужно запоминать все больше и больше чисел

Рекурсивный процесс — это процесс с отложенным вычислением.

Итеративный процесс постоянно говорит «я сейчас посчитаю все что можно и продолжу» на каждом шаге рекурсии. Ему не нужно ничего запоминать вне вызова, он всегда все считает в первый возможный момент. Каждый шаг рекурсии может существовать в изоляции от прошлых, потому что вся информация передается последовательно.

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

А на этой картинке видно, что использование памяти не растет.

Подытожим в шуточной форме. Рекурсивный процесс — это чувак, который все дела откладывает на вечер пятницы. В течение недели у него мало работы, а в пятницу завал. Но ему так нравится.

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

Что такое рекурсивные функции и в чем особенность их применения

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

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

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

Читайте также: Как проверить качество кода: функциональное и нефункциональное тестирование

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

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

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

Что такое хвостовая рекурсия

Как использовать преимущества итеративного процесса и одновременно избавиться от недостатка рекурсивных функций, то есть от неумолимого роста использования памяти? Можно избавить процесс от заполнения стека «ненужными» контекстами предыдущих вызовов и обеспечить прямой возврат из функции при достижении терминального условия.

Для этого служит так называемая оптимизация хвостовой рекурсии (Tail call optimization). Итеративный процесс, который мы рассмотрели, как раз можно отнести к хвостовой рекурсии. Благодаря оптимизации состояния стека, она придает итеративному процессу вид «плоской» итерации. Так исключается его переполнение из-за большой глубины рекурсии.

Хвостовая рекурсия и ее оптимизация широко используется при написании программ на функциональных языках программирования.

Бесплатные курсы по программированию в Хекслете

  • Освойте азы современных языков программирования
  • Изучите работу с Git и командной строкой
  • Выберите себе профессию или улучшите навыки

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

Рекурсия

Язык 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

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

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