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

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

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

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

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

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

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

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

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

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

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

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

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 целых неотрицательных числа 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)); // вызов рекурсивной функции
    }
}