Основы Java-рекурсии

Надеюсь, вы наконец-то поняли, что рекурсия — это все, что относится к себе (если нет, то вы можете застрять в Google навсегда, пытаясь выяснить, что такое рекурсия!). Довольно распространенным примером рекурсии являются числа Фибоначчи. Шаблон для чисел Фибоначчи состоит в том, чтобы сложить 2 предыдущих термина вместе для следующего термина, начиная с одного и одного.

Ниже приведено рекуррентное соотношение для чисел Фибоначчи:

F (1) = F (2) = 1
F (n) = F (n-1) + F (n-2)

Отношение повторения — это любое отношение, в котором исходная функция ссылается на себя. Итак, как нам найти F (5)?

F (5) = F (4) + F (3)
F (5) = [F (3) + F (2)] + [F (2) + F (1)] F (5) = [F (2) + F (1)] + 1 + 1 + 1
F (5) = 1 + 1 + 1 + 1 + 1
F (5) = 5

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

Так, каковы все части рекурсивной функции? Прежде всего, что такое рекурсивная функция? Рекурсивная функция — это любая функция, которая вызывает себя (прямо или косвенно). Вот простой пример на Java:

Конечно, это в конечном итоге приведет к ошибке потока в стеке, поэтому не рекомендуется пробовать этот код по-настоящему.

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

1. Определены базовые случаи (случаи, когда решение очевидно и не может быть уменьшено в дальнейшем)
2. Шаг сокращения (место, чтобы упростить данную проблему)
3. Рекурсивный вызов сам по себе (в основном решает более простой случай)

В приведенной выше рекурсивной функции Фибоначчи вы можете видеть, что она рекурсивна до тех пор, пока не сложит 1. Это потому, что в последовательности Фибоначчи 1 является базовым случаем, поэтому нам просто нужно сложить 1 несколько раз, чтобы получить F (n).

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

Давайте посмотрим на факториальную функцию рекурсивно и сравним ее с итеративными родственниками.

Факториал (N) = 1 * 2 * 3 *… * N
В основном, умножьте все целые числа от 1 до N, чтобы получить факториал числа N.

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

Мы также можем написать рекурсивный эквивалент этой функции: F (1) = 1 F (N) = F (N-1) * N. Вы видите, как это даст те же результаты, что и итеративный факториал? Вот код для рекурсивного вычисления факториалов:

Итак, с точки зрения производительности, как рекурсия складывается здесь с итеративным решением? К сожалению, ответ довольно плохо. Здесь рекурсивной функции требуется много памяти для хранения стека методов и отслеживания всех переменных в каждом рекурсивном вызове, в то время как итеративные решения должны отслеживать только текущее состояние. Так зачем вообще заниматься рекурсией? Потому что во многих случаях, когда рекурсия используется правильно, ее производительность может быть выше, чем у итеративных решений, и рекурсивные функции также легче писать (иногда).

Динамическое программирование

Динамическое программирование — это форма рекурсии, но она реализуется итеративно. Помните наш компьютер Фибоначчи выше? F (5) = F (2) + F (1) + F (2) + F (2) + F (1) F (5) = 3 * F (2) + 2 * F (1) несколько «перерасчетов» здесь. Необходимо было только вычислить F (2) один раз и F (1) один раз. В этом случае вычисление этих нескольких терминов было не слишком сложной задачей, но в некоторых ситуациях становится практически невозможным пересчитывать решения сотни раз. Таким образом, вместо повторного вычисления, мы храним ответ.

Итак, возьмите F (5) снова. Если бы мы делали это рекурсивным способом, это было бы 8 вызовов recursiveFibonacci. Однако здесь мы только вычислили F (1), F (2), F (3), F (4) и F (5) один раз. Это увеличение на 3 вызова может показаться не таким уж большим, но что если мы попробуем вычислить F (50)? dynamicFibonacci вычислит только 50 чисел, но recursiveFibonacci может занять более 1000 (конечно, я не учел, поэтому не знаю, больше 1000 или нет).

Последнее замечание о динамическом программировании заключается в том, что оно помогает только в тех случаях, когда у нас тонны оверлапа. Помните функцию recursiveFactorial? Если мы вызовем recursiveFactorial (50) и dynamicFactorial (50), они будут выполняться примерно одинаково, потому что мы выполняем одинаковое количество вычислений. Это потому, что нет никакого наложения на колени. Именно поэтому алгоритмы сортировки являются плохим выбором для реализации с динамическим программированием: если вы анализируете большинство алгоритмов сортировки, у них почти нет перекрывающихся решений, что является плохим кандидатом для динамического программирования.

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

1. Реализуйте метод recursiveFactorial (и вы подумали, что я забыл поместить это туда)
2. Для данного рекурсивного отношения напишите рекурсивный метод, который найдет F (N)
3. Что означает это рекурсивное отношение в итерационных терминах? Напишите итеративное решение этой проблемы.
4. Являются ли эти рекурсивные отношения хорошим кандидатом для динамического программирования? Почему, почему нет?
5. Есть ли лучший способ решить эту проблему, чем итеративные или рекурсивные решения? Что это (если есть)? Подсказка: подумайте о Карле Гауссе

Для задач 2-5 используйте это рекурсивное отношение:
F (1) = 1
F (N) = F (N-1) + N

Ответы должны прийти …

Ссылка: рекурсия от наших партнеров JCG на форумах по программированию на Java

Статьи по Теме :

• Java Micro-Benchmarking: Как правильно писать тесты
• Первичная причина регистрации исключений
• Программирование антипаттернов
• Топ 10 книг на Java, которые вы не хотите пропустить
• Java Logging Mess
• Делай это коротко, но делай это правильно!