Введение в рекурсию

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

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

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

Итак, с циклами, зачем использовать рекурсию? ?В некоторых случаях (последовательности Фибоначчи, Ханойские башни) рекурсия намного проще, чем цикл.
Бесполезно говорить слишком много, давайте почувствуем рекурсию.

Мы, должно быть, делали подобные упражнения, когда впервые изучали программирование:

1+2+3+4+....+100(n)сумма
Учитывая массив, найти максимальное значение внутри массива

Что мы должны помнить, так это то, что для использования рекурсии мы должны знать два условия:

Рекурсивный выход (условие прекращения рекурсии)
рекурсивное выражение (правило)

Совет: в рекурсии часто нужно поставить задачуразрезать на две части (1 и всю идею), что позволяет нам быстро находить рекурсивные выражения (правила)

1. Примирение

если мы используемforцикл для суммирования1+2+3+4+....+100, это так же просто, как:


    int sum = 0;
    for (int i = 1; i <= 100; i++) {

        sum = sum + i;

    }
    System.out.println("公众号：Java3y：" + sum);

Как я уже говорил ранее, циклы for можно переписать с помощью рекурсии, а для использования рекурсии необходимо знать два условия: 1. Рекурсивный выход, 2. Рекурсивное выражение (правило)

Во-первых, давайте выясним его правила:1+2+3+...+n, что является операцией суммирования, то можно считатьX=1+2+3+...+n,могу1+2+3+...+(n-1)рассматривается какв общем и целом. И это целое делает то же самое, что и наша **первоначальная цель (суммирование)**. С нашими знаниями математики средней школы мы можем увидеть приведенную выше формулу какX=sum(n-1)+n

Итак, мы находим наше рекурсивное выражение (закон), котороеsum(n-1)+n, Насчет рекурсивного выхода, рекурсивных выходов по этой теме много, перечислю их:

еслиn=1, затем вернуться1
еслиn=2, затем вернуться3(1+2)
еслиn=3, затем вернуться6(1+2+3)

Конечно, я должен был использовать один из самых простых рекурсивных выходов:if(n=1) return 1

Мы нашли как рекурсивные выражения, так и рекурсивные выходы Вот демонстрация кода:

Рекурсивный выход равен 1:


    public static void main(String[] args) {
        System.out.println("公众号：Java3y：" + sum(100));
    }

    /**
     *
     * @param n 要加到的数字，比如题目的100
     * @return
     */
    public static int sum(int n) {
        
        if (n == 1) {
            return 1;
        } else {
            return sum(n - 1) + n;
        }
    }

Рекурсивный выход равен 4:


    public static void main(String[] args) {
        System.out.println("公众号：Java3y：" + sum(100));
    }

    /**
     *
     * @param n 要加到的数字，比如题目的100
     * @return
     */
    public static int sum(int n) {

        //如果递归出口为4，(1+2+3+4)
        if (n == 4) {
            return 10;
        } else {
            return sum(n - 1) + n;
        }
    }

Результат тот же.

Во-вторых, максимальное значение внутри массива

Если использовать цикл, то обычно делаем так:


    int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2};

    //将数组的第一个假设是最大值
    int max = arrays[0];

    for (int i = 1; i < arrays.length; i++) {

        if (arrays[i] > max) {
            max = arrays[i];
        }
    }

    System.out.println("公众号：Java3y：" + max);

Итак, если мы используем рекурсию, как ее использовать? первый, кто нашелРекурсивные выражения (правила) и рекурсивные выходы

Мы можем использовать 1 и всю идею, чтобы найти закон
- поместите первое число в массив ->2с номером после массива ->{3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}провестирезать, обработайте число после массива какв общем и целомX={3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}, то мы можем видеть, чтоПервое число сравнивается с целымif(2>X) return 2 else(2<X) return X
- И все, что нам нужно сделать, это выяснить этов общем и целоммаксимальное значение2Сравнивать. выяснитьв общем и целомМаксимальное значение совпадает с нашей **первоначальной целью (нахождение максимального значения)**
- также можно записать какif( 2>findMax() )return 2 else return findMax()
Рекурсивный выход, если в массиве всего 1 элемент, то максимальное значение массива это он.

При использовании массива мы обычно задаем левую и правую границы массива, чтобы лучше обрезать

L представляет левую границу, которая часто представляет первый элемент массива, и ему также будет присвоено значение 0 (метка угла 0 является первым элементом массива)
R представляет собой правую границу, которая часто представляет собой длину массива, а также будет назначена какarrays.length-1(Длина-1 — это последний элемент в метке угла)

Затем мы можем посмотреть на нашу рекурсивную запись:



  public static void main(String[] args) {

        int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};

        System.out.println("公众号：Java3y：" + findMax(arrays, 0, arrays.length - 1));


    }
  

    /**
     * 递归，找出数组最大的值
     * @param arrays 数组
     * @param L      左边界，第一个数
     * @param R      右边界，数组的长度
     * @return
     */

    public static int findMax(int[] arrays, int L, int R) {

        //如果该数组只有一个数，那么最大的就是该数组第一个值了
        if (L == R) {
            return arrays[L];
        } else {

            int a = arrays[L];
            int b = findMax(arrays, L + 1, R);//找出整体的最大值

            if (a > b) {
                return a;
            } else {
                return b;
            }
        }

    }

3. Рекурсивное написание пузырьковой сортировки

В главе о пузырьковой сортировке дана рекурсивная реализация пузырьковой сортировки на языке C, так что теперь, когда мы использовали основную идею рекурсии, давайте перепишем ее на Java:

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

Преобразование с рекурсивным мышлением:

Когда первый проход отсортирован, мы можем отсортировать последнюю цифру (R) массива с числом перед массивом (L, R-1).резать, число (L, R-1) перед массивом рассматривается какв общем и целом, в целом это то же самое, что и наша **первоначальная цель (найти максимальное значение и обменять его на конец текущего количества проходов)**
Рекурсивный выход: когда есть только один элемент, нет необходимости сравнивать:L==R


    public static void main(String[] args) {

        int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};
        bubbleSort(arrays, 0, arrays.length - 1);
        System.out.println("公众号：Java3y：" + arrays);


    }

    public static void bubbleSort(int[] arrays, int L, int R) {

        int temp;

        //如果只有一个元素了，那什么都不用干
        if (L == R) ;

        else {
            for (int i = L; i < R; i++) {
                if (arrays[i] > arrays[i + 1]) {
                    temp = arrays[i];
                    arrays[i] = arrays[i + 1];
                    arrays[i + 1] = temp;
                }
            }

            //第一趟排序后已经将最大值放到数组最后面了

            //接下来是排序"整体"的数据了
            bubbleSort(arrays, L, R - 1);

        }
    }

В-четвертых, последовательность Фибоначчи

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

Последовательность Фибоначчи выглядит так:{1 1 2 3 5 8 13 21 34 55..... n }

Учащиеся, хорошо разбирающиеся в математике, могут легко найти правила:Сумма первых двух равна третьему

Например:

 	1 + 1 = 2
	2 + 3 = 5
	13 + 21 = 34

Если мы спросим, что такое n-й член, то мы можем просто написать соответствующее рекурсивное выражение:Z = (n-2) + (n-1)

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

Точно так же наш рекурсивный выход может быть записан как:if(n==1) retrun 1 if(n==2) return 2

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


    public static void main(String[] args) {

        int[] arrays = {1, 1, 2, 3, 5, 8, 13, 21};
        //bubbleSort(arrays, 0, arrays.length - 1);

        int fibonacci = fibonacci(10);
        System.out.println("公众号：Java3y：" + fibonacci);


    }

    public static int fibonacci(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 1;
        } else {
            return (fibonacci(n - 1) + fibonacci(n - 2));
        }

    }

5. Алгоритм Ханойской башни

Источник изображения Энциклопедия Baidu:

Правила игры в Ханойскую башню просты:

Есть три столба, первоначальный, заполненный пластинами разных размеров, мы называем А, и два пустых столба, которые мы называем В и С (необязательно).
Конечная цельПереместите все тарелки из столбца А в столбец С.
- При переезде есть правило:Одновременно можно перемещать только одну тарелку, маленькие тарелки не могут быть поверх больших тарелок (наоборот: большие тарелки не могут ложиться поверх маленьких тарелок)

Давайте поиграем с этим:

Табличка только одна:
- будетПластина колонны А перемещается непосредственно в колонну С.
- завершить игру
Табличек всего две:
- на стойке АнебольшойТабличка перенесена на среднюю стойку
- на стойке АБольшойТабличка перенесена на заднюю стойку
- будет в конце средней стойкинебольшойПластина перемещается на заднюю стойкуБольшойпластина
- завершить игру
Табличек всего три:
- Столбнебольшойпереместите пластину на заднюю стойку
- на стойке АсерединаТабличка перенесена на среднюю стойку
- Поставить заднюю стойкунебольшойПластина перемещается к средней стойкесерединапластина
- столбБольшойТабличка перенесена на заднюю стойку
- стойка ВнебольшойТабличка перенесена на переднюю стойку
- стойка ВсерединаТабличка перенесена на заднюю стойку
- Наконец, передняя стойканебольшойТабличка перенесена на заднюю стойку
- завершить игру

.......................

Правила, которые мы можем найти в первых трех играх:

Чтобы переместить самую большую пластину на заднюю стойку, необходимо переместитьПереместите остальные пластины к центральной стойке (с помощью центральной стойки переместите самую большую пластину к центральной стойке [переместите все пластины, кроме самой большой, к центральной стойке])[рекурсивное выражение]
Когда на задней стойке установлена самая большая пластина, все пластины находятся в центральной стойке. Теперь цельИспользуйте столб A, чтобы поместить все пластины столба B в столб C (то же, что и выше, произошла рекурсия)
Когда есть только одна пластина, вы можете перейти прямо к задней стойке (рекурсивный выход)
- Столб A называется стартовым столбом, столб B называется промежуточным столбом, а столб C называется целевым столбом.
- Из вышеприведенного описания мы можем обнаружить, что роли стартового и промежуточного столпов изменятся (столп А является стартовым в начале и становится промежуточным столбом после второго раунда. Столп В является целевым столбом). в начале и после второго раунда он стал отправной точкой.Роли стартового столба и промежуточного столба постоянно меняются местами.)

Проще говоря, он делится на три этапа:

Переместите пластину n-1 на передаточную стойку
Переместите самую большую пластину из начальной точки в целевую стойку.
Также переместите пластину n-1 транспортной колонки в целевую колонку.

Затем вы можете написать код для его тестирования (оглянитесь на процесс воспроизведения выше):


    public static void main(String[] args) {

        int[] arrays = {1, 1, 2, 3, 5, 8, 13, 21};
        //bubbleSort(arrays, 0, arrays.length - 1);

        //int fibonacci = fibonacci(10);

        hanoi(3, 'A', 'B', 'C');

        System.out.println("公众号：Java3y" );


    }

    /**
     * 汉诺塔
     * @param n n个盘子
     * @param start 起始柱子
     * @param transfer 中转柱子
     * @param target 目标柱子
     */
    public static void hanoi(int n, char start, char transfer, char target) {


        //只有一个盘子，直接搬到目标柱子
        if (n == 1) {
            System.out.println(start + "---->" + target);
        } else {

            //起始柱子借助目标柱子将盘子都移动到中转柱子中(除了最大的盘子)
            hanoi(n - 1, start, target, transfer);
            System.out.println(start + "---->" + target);

            //中转柱子借助起始柱子将盘子都移动到目标柱子中
            hanoi(n - 1, transfer, start, target);

        }
    }

Давайте проверим, правильно ли мы пишем:

Использованная литература:

Ууху. Call.com/question/24…

6. Резюме

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

Чтобы использовать рекурсию, вам сначала нужно знать две вещи:

Рекурсивный выход (условие прекращения рекурсии)
рекурсивное выражение (правило)

Идея «целого» часто используется в рекурсии, и пример с Ханойской башней не исключение:Считайте тарелку с самой большой тарелкой за 1, а тарелку выше в целом.. Тогда мы очень ясно, когда мы вычисляем:Переместите «целое» на среднюю стойку, переместите самую большую пластину на заднюю стойку и, наконец, переместите пластину средней стойки на заднюю стойку.

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

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

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

PS:Если есть способ лучше понять, или я что-то не так понял, вы можете оставить сообщение в комментариях, чтобы пообщаться вместе!

Если в статье есть ошибки, пожалуйста, исправьте меня и поделитесь друг с другом. Учащиеся, привыкшие читать технические статьи в WeChat и желающие получить больше ресурсов по Java, могутОбратите внимание на публичный аккаунт WeChat: Java3y