Кратко о рекурсии. Задачи на рекурсию | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
Team Lead Архитектура и шаблоны проектирования Разработчик IoT C# Developer. Professional PostgreSQL Подготовка к сертификации Oracle Java Programmer (OCAJP) C# ASP.NET Core разработчик
-5%
Kotlin Backend Developer
-8%
iOS Developer. Professional
-8%
Symfony Framework Unity Game Developer. Basic JavaScript Developer. Professional Android Developer. Basic JavaScript Developer. Basic Java Developer. Professional Highload Architect Reverse-Engineering. Professional Java Developer. Basic PHP Developer. Professional Алгоритмы и структуры данных Framework Laravel Cloud Solution Architecture Vue.js разработчик Интенсив «Оптимизация в Java» Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив "Tarantool" PHP Developer. Basic
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK Дизайн сетей ЦОД Разработчик IoT PostgreSQL Экспресс-курс "Версионирование и командная работа с помощью Git"
-30%
Экспресс-курс «Введение в непрерывную поставку на базе Docker» Базы данных Reverse-Engineering. Professional Administrator Linux. Professional Network engineer Cloud Solution Architecture Внедрение и работа в DevSecOps Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив «СУБД в высоконагруженных системах» Супер-интенсив "Tarantool" Network engineer. Basic
Корпоративные курсы
Безопасность веб-приложений IT-Recruiter Дизайн сетей ЦОД Компьютерное зрение Разработчик IoT Вебинар CERTIPORT Machine Learning. Professional
-6%
NoSQL Пентест. Практика тестирования на проникновение Java QA Engineer. Базовый курс Руководитель поддержки пользователей в IT
-8%
SRE практики и инструменты Cloud Solution Architecture Внедрение и работа в DevSecOps Супер-практикум по работе с протоколом BGP Infrastructure as a code Супер-практикум по использованию и настройке GIT Промышленный ML на больших данных Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes» BPMN: Моделирование бизнес-процессов Основы Windows Server
Специализации Курсы в разработке Подготовительные курсы Подписка
+7 499 938-92-02

Кратко о рекурсии. Задачи на рекурсию

Java_Deep_23.8-5020-afdbad.png

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

Пример бесконечной рекурсии в литературе — докучные сказки типа «У попа была собака», где конец подменяется началом и всё продолжается снова и снова. А вот ещё примеры рекурсии:

1-20219-b3a480.jpg

О рекурсии в программировании

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

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

Как решают задачи на на рекурсию?

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

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

Если мы решаем сложную задачу (небазового случая), мы выполняем несколько рекурсивных вызовов либо шагов, т. к. наша цель — упростить задачу. И делать это до тех пор, пока не придём к базовому решению.

Ещё раз. Рекурсивная функция включает в себя: — базовый случай, он же условие остановки; — шаг рекурсии, он же условие продолжения.

Давайте рассмотрим это, изучив пример нахождения факториала:

public class Solution { 
    public static int recursion(int n) {
        // условие выхода
        // Базовый случай
        // когда остановиться/повторять рекурсию ?
        if (n == 1) {
            return 1;
        }
        // Шаг рекурсии/рекурсивное условие
        return recursion(n - 1) * n;
    }
    public static void main(String[] args) {
        System.out.println(recursion(5)); // вызов рекурсивной функции
    }
}

Здесь базовое условие — когда n=1. Раз мы знаем что 1!=1, для вычисления 1! нам ничего не надо. И чтобы определить 2! Можно использовать 1!, то есть 2!=1!2. А чтобы вычислить 3! потребуется 2!3… Для вычисления n! нужно (n-1)!*n. Вот это и есть шаг рекурсии. Другими словами, чтоб нам получить значение факториала от числа n, нам достаточно умножить на n значение факториала от предыдущего числа.

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

Задача о рекурсии № 1: От 1 до n

У вас есть натуральное число n. Необходимо вывести все числа от 1 до n.

Решение:

public class Solution {
    public static String recursion(int n) {
        // Базовый случай
        if (n == 1) {
            return "1";
        }
        // Шаг рекурсии/рекурсивное условие
        return recursion(n - 1) + " " + n;
    }
    public static void main(String[] args) {
        System.out.println(recursion(10)); // вызов рекурсивной функции
    }
}

Задача о рекурсии № 2. От А до В

Имеются 2 целых числа A и В (каждое из них в отдельной строке). Необходимо вывести все числа от A до B включительно. Если A < B, числа выводятся по возрастанию, в обратном случае — по убыванию.

Решение:

public class Solution {
    public static String recursion(int a, int b) {
            // основное условие задачи
        if (a > b) {
            // Базовый случай
            if (a == b) {
                return Integer.toString(a);
            }
            // Шаг рекурсии/рекурсивное условие
            return a + " " + recursion(a - 1, b);
        } else {
            // Базовый случай
            if (a == b) {
                return Integer.toString(a);
            }
            // Шаг рекурсии/рекурсивное условие
            return a + " " + recursion(a + 1, b);
        }
    }
    public static void main(String[] args) {
        System.out.println(recursion(20, 15)); // вызов рекурсивной функции
        System.out.println(recursion(10, 15)); // вызов рекурсивной функции
    }
}

Задача о рекурсии № 3. Функция Аккермана

Функция Аккермана A(m,n), играет важную роль в теории вычислимости. Она определена следующим образом:

2-20219-fdf00d.jpg

Условие задачи: есть 2 целых неотрицательных числа m и n, каждое из них находится в отдельной строке. Необходимо вывести A(m,n).

Решение:

public class Solution {
    public static int recursion(int m, int n) {
        // Базовый случай
        if (m == 0) {
            return n + 1;
        } // Шаг рекурсии/рекурсивное условие
        else if (n == 0 && m > 0) {
            return recursion(m - 1, 1);
        } // Шаг рекурсии/рекурсивное условие
        else {
            return recursion(m - 1, recursion(m, n - 1));
        }
    }
    public static void main(String[] args) {
        System.out.println(recursion(3, 2)); // вызов рекурсивной функции
    }
}

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться