Понимание рекурсии в одной статье

алгоритм

предисловие

Рекурсия - очень важная идея в алгоритме, и она имеет широкий спектр применения, она такая же маленькая, как факториал, и она используется в работе, например, для подсчета размера папок, и это видно по алгоритму Google PageRank. , Это также фаворит интервьюеров.

В последнее время я прочитал много рекурсивных статей и многому научился.Однако я обнаружил, что большинство статей о рекурсии в Интернете не являются исчерпывающими.Основная проблема в том, что большинство из них не дает соответствующего времени/ пространственной сложности после решения задачи.Временная/пространственная сложность является важным фактором алгоритма!Временная сложность рекурсивных алгоритмов, как правило, сложна (необходимы методы индукции и т. д.), другими словами, если сложность рекурсивного алгоритма может быть решена, временная сложность других проблем алгоритма Степени в основном не может быть и речи. Кроме того, временная сложность рекурсивного алгоритма неприемлема. Если расчетная временная сложность окажется слишком большой, вам необходимо изменить свое мышление и посмотреть, есть ли лучшее решение. Это основная цель. ради рекурсии. !

В этой статье делается попытка объяснить рекурсию со следующих аспектов.

  1. Что такое рекурсия?
  2. Общая идея решения рекурсивного алгоритма
  3. Практические упражнения (от начального до продвинутого)

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

что такое рекурсия

Проще говоря, если возникает ситуация, при которой вызывается сама функция, то это явление называется рекурсией.

Взяв в качестве примера иерархическую функцию, как показано ниже, в факториальной функции есть вызов factorial(n - 1), поэтому эта функция является рекурсивной функцией.

public int factorial(int n) {
    if (n < =1) {
        return 1;
    }
    return n * factorial(n - 1)
}

Для дальнейшего анализа «рекурсии» сначала идет «доставка», а затем «возврат», «доставка» означает разложение проблемы на подзадачи для решения, а затем подзадачи разлагаются на подподзадачи,.. ., пока не разобрали Подзадачу не нужно разбивать на более мелкие подзадачи (которые могут быть решены), "возврат" означает, что решается самая маленькая подзадача, затем решается и ее подзадача верхнего уровня решена, и подзадача верхнего уровня решена. Теперь верхняя и верхняя подзадачи естественным образом решены.... Пока не решена исходная проблема, текст может быть немного абстрактным, поэтому давайте возьмем класс f( 6) в качестве примера увидеть его «доставку» и «возврат».

Чтобы решить проблему f (6), поскольку f (6) = n * f (5), f (6) необходимо разложить на f (5) подзадач для решения, аналогично f (5) = n * f (4 ) , также необходимо разбить дальше,... , пока f(1), это "прохождение", f(1) решено, так как f(2) = 2 f(1) = 2 также решено ,... .. f(n) также решается в конце, то есть "возврате", поэтому суть рекурсии состоит в том, чтобы разбить задачу натакое же решениеподзадача, . . . Пока окончательно разобранные подзадачи уже нельзя разделить, после решения подзадач, которые можно решить с наименьшей степенью детализации, исходная задача естественно решается в процессе «возврата».

Общая идея решения рекурсивного алгоритма

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

  1. Проблема может быть разложена на наличиетакое же решениеподзадачи, под-подпроблемы, другими словами, все эти проблемыможет вызвать ту же функцию
  2. Подзадачи, которые были декомпозированы слой за слоем, в итоге должны иметь фиксированное значение, которое не может быть декомпозировано (то есть условие прекращения), иначе подзадачи будут декомпозироваться бесконечно, и проблема заведомо неразрешима.

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

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

  1. Сначала определите функцию,уточнить назначение этой функции, потому что рекурсия характеризуется тем, что и проблема, и подзадачи будут вызывать саму функцию, поэтому, как только функция этой функции определена, остается только найти рекурсивную связь между проблемой и подзадачей.
  2. Затем найдите взаимосвязь между проблемой и подпроблемами (т.формула рекурсии), так что, поскольку проблема и подзадачи имеюттакое же решение, пока подзадача вызывает функцию, определенную на шаге 1, проблема может быть решена. Так называемые отношения лучше всего представлены формулой, такой какf(n) = n * f(n-)Таким образом, если пока нельзя получить четкую формулу, ее также можно выразить в псевдокоде.После нахождения рекуррентного соотношения необходимо найти решение итоговой подзадачи, которое не может быть повторно декомпозировано , то есть (критическое условие), чтобы гарантировать, что подзадача не будет декомпозироваться бесконечно вниз. Поскольку мы определили функцию этой функции на первом шаге, когда проблема разбита на подзадачи, подзадача может вызывать функцию, определенную на шаге 1, которая удовлетворяет рекурсивным условиям (функция вызывает сама себя)
  3. Рекурсивная формула второго шага выражается в коде и добавляется к функции, определенной на шаге 1.
  4. Наконец, это также очень важный шаг.В соответствии с соотношением между проблемой и подзадачами определяется временная сложность.Если рекурсивная временная сложность оказывается неприемлемой, необходимоИзмените свое мышление, чтобы увидеть, есть ли более надежное решение

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

Практические упражнения (от начального до продвинутого)

Разминочный матч

Введите целое положительное число n, выведите значение n!. где п!=123*…*n, то есть найти факториал

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

  1. Определите эту функцию и уточните функцию этой функции.Мы знаем, что функция этой функции состоит в том, чтобы найти факториал n, а затем найти факториал n-1, n-2, мы можем назвать эту функцию
/**
 * 求 n 的阶乘
 */
public int factorial(int n) {
}

2. Найдите связь между проблемой и подпроблемой Отношение факториала относительно простое, мы используем f(n) для представления факториала n, очевидно, f(n) = n * f(n - 1), а критическим условием является f(1) = 1, то есть

f(n)= \begin{cases} 1, n = 1 \\ n * f(n-1) \end{cases}

3. Рекурсивная формула второго шага выражается в коде и добавляется к функции, определенной на шаге 1.

/**
 * 求 n 的阶乘
 */
public int factorial(int n) {
    // 第二步的临界条件
    if (n < =1) {
        return 1;
    }

    // 第二步的递推公式
    return n * factorial(n-1)
}

4. Найдите временную сложность Поскольку f(n) = n * f(n-1) = n * (n-1) * .... * f(1), всего выполняется n умножений, поэтому временная сложность равна n.

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

Вводные вопросы

一只青蛙可以一次跳 1 级台阶或者一次跳 2 级台阶，例如：

Есть только один способ перейти к первому шагу: просто перейти к первому шагу. Есть два способа подпрыгнуть на 2-ю ступеньку: по 1 ступени за раз дважды или по 2 ступени за раз. Сколькими способами можно запрыгнуть на n-ю ступеньку?

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

1. Определите функцию, представляющую метод прыжка вверх на n шагов.

/**
 * 跳 n 极台阶的跳法
 */
public int f(int n) {
}

2. Найдите связь между проблемой и подпроблемой На первый взгляд кажется, что отношения между ними не имеют никаких подсказок, но если вы внимательно посмотрите на название, лягушка может прыгнуть только на один или два шага.Думайте сверху вниз, то есть если вы хотите перепрыгнуть на n шагов, вы можете прыгнуть только с n-1 или n-2, поэтому задача трансформируется в метод прыжков с прыжками на n-1 и n-2 шагов, если f(n) представляет метод прыжка с переходом на n шагов, тогда из приведенного выше анализа мы можем получить f(n) = f(n-1) + f(n-2), очевидно, это связь между проблемой, которую мы ищут и подзадачу, И, очевидно, при n = 1, n = 2, то есть прыжок на один или два шага является окончательным решением задачи, поэтому рекурсивная формула

f(n)= \begin{cases} 1, n = 1 \\ 2, n = 2 \\ f(n-1) + f(n-2) \end{cases}

3. Рекурсивная формула второго шага выражается в коде и добавляется к функции, определенной на шаге 1. Добавленная функция выглядит следующим образом

/**
 * 跳 n 极台阶的跳法
 */
public int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return f(n-1) + f(n-2)
}

4. Сложность времени вычислений Из вышеприведенного анализа видно, что f(n) удовлетворяет следующей формуле

f(n)= \begin{cases} 1, n = 1 \\ 2, n = 2 \\ f(n-1) + f(n-2) \end{cases}

Вычисление временной сложности Фибоначчи требует знания продвинутой алгебры. Здесь нет подробного вывода. Заинтересованные студенты могут нажатьздесьПросмотр, непосредственно делаем выводы

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

Видно, что много повторных вычислений, f(3) вычисляется 3 раза, и с увеличением n время f(n) естественно увеличивается экспоненциально

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

public int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    // map 即保存中间态的键值对， key 为 n，value 即 f(n)
    if (map.get(n)) {
        return map.get(n)
    }
    return f(n-1) + f(n-2)
}

Итак, какова временная сложность после преобразования?Поскольку мы сохраняем промежуточное состояние для каждого вычисленного f(n), нет проблемы повторного вычисления, поэтому временная сложность равна O(n), но поскольку мы используем ключ-значение пара используется для хранения промежуточных результатов вычислений, поэтому объемная сложность равна O(n). На самом деле проблема здесь решена, но как программисты с преследованием мы все еще должны спросить, можно ли продолжить оптимизацию пространственной сложности?

5. Используйте итерации цикла, чтобы обновить алгоритм Мы анализируем отношения проблема-подпроблема (f(n) = f(n-1) + f(n-2)) когда используешьнизходящий, но на самом деле, когда мы решаем f(n), мы можем использоватьвверх дномспособ решения, путем наблюдения мы можем найти следующие правила

f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 3
f(4) = f(3) + f(2) = 5
....
f(n) = f(n-1) + f(n-2)

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

public int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;

    int result = 0;
    int pre = 1;
    int next = 2;
    
    for (int i = 3; i < n + 1; i ++) {
        result = pre + next;
        pre = next;
        next = result;
    }
    return result;
}

Временная сложность после преобразования составляет O(n), а поскольку в процессе вычисления мы определяем только две переменные (pre, next), пространственная сложность составляет O(1).

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

основные вопросы

Далее давайте рассмотрим следующую классическую тему: инвертирование бинарного дерева. Преобразовать левое бинарное дерево в правое бинарное дерево

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

1. Определите функцию, которая представляет переворачивание бинарного дерева с корнем в качестве корневого узла.

public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public TreeNode invertTree(TreeNode root) {
}

2. Найдите связь между проблемой и подзадачей и получите рекурсивную формулу Как мы уже говорили ранее, нам нужно использовать мышление сверху вниз для решения проблем.Затем мы берем предыдущие узлы 1, 2 и 3. Для корневого узла 1 предполагается, что узлы под узлами 2 и 3 были Flip, затем просто переверните 2 и 3 узлы, чтобы удовлетворить спрос

Для узлов 2 и 3 просто переверните левый и правый узлы и т. д. Для каждого корневого узла переверните левый и правый узлы по очереди, чтобы мы знали, что связь между проблемой и подзадачей flip (корневой узел) = flip (левый узел корневого узла) + flip (правый узел корневого узла) который инвертировать (корень) = инвертировать (корень-> влево) + инвертировать (корень-> вправо)

И, очевидно, условием завершения рекурсии является завершение, когда узел является листовым узлом (поскольку листовой узел не имеет левого и правого узлов)

3. Рекурсивная формула второго шага выражается в коде и добавляется к функции, определенной на шаге 1.

 public TreeNode invertTree(TreeNode root) {
    // 叶子结果不能翻转
    if (root == null) {
        return null;
    }
    // 翻转左节点下的左右节点
    TreeNode left = invertTree(root.left);
    // 翻转右节点下的左右节点
    TreeNode right = invertTree(root.right);

    // 左右节点下的二叉树翻转好后，翻转根节点的左右节点
    root.right = left;
    root.left = right;
    return root;
}

4. Анализ временной сложности Поскольку мы будем переворачивать каждый узел, временная сложность будет O(n). А как насчет пространственной сложности? Пространственная сложность этого вопроса очень интересна. Давайте посмотрим на нее, потому что каждый вызов функции invertTree эквивалентен к операции проталкивания стека. Сколько раз стек проталкивается самое большее? Посмотрите внимательно на следующий код вышеприведенной функции.

    TreeNode left = invertTree(root.left);

Начиная с корневого узла, функция flip непрерывно вызывается для левого результата до конечного узла.Каждый вызов будет толкать стек.После вызова левого узла стек будет извлечен, а затем будет перемещен правый узел. стек.... На следующем рисунке показано, что размер стека равен 3, то есть высоте дерева, если это полное бинарное дерево, высота дерева равна logn, то есть пространственной сложности равно O(logn),

В худшем случае, если бинарное дерево такое, как показано на рисунке (только левый узел, без правого узла), высота дерева равна количеству узлов n, а пространственная сложность равна O(n). , Сложность пространства O (n)

В качестве отступления, этот вопрос вызвал сенсацию в начале, потому что Макс Хауэлл, автор известного доморощенного инструмента управления пакетами под Mac, сначала не мог решить этот вопрос, но он был отвергнут Google, то есть если ты решил этот вопрос, превзошел этого мирового бога, подумай об этом, это очень увлекательно

Промежуточные вопросы

Теперь давайте взглянем на задачу о Ханойской башне, которую мы изучали в колледже: Как показано на рисунке ниже, слева направо расположены три столба A, B и C. Среди них n дисков, уложенных от малого к большому на столбе A. Теперь требуется переместить диск на столбе A на столб C. В течение периода, только Принцип: Вы можете двигаться только к одной тарелке за раз, и большая тарелка не может быть на маленькой тарелке Найдите шаги и количество ходов.

Затем примените наш рекурсивный четырехэтапный метод, чтобы увидеть, как решить эту проблему.

1. Определить рекурсивную функцию задачи и уточнить функцию функции.Определим функцию этой функции как: переместить n дисков выше A в C через B

// 将 n 个圆盘从 a 经由 b 移动到 c 上
public void hanoid(int n, char a, char b, char c) {
}

2. Найдите связь между проблемой и подпроблемой Сначала посмотрим, как двигаться, если на передней стойке всего два диска.

Ранее мы много раз упоминали, что взаимосвязь между проблемой и подзадачей следует анализировать нисходящим образом.Чтобы переместить n дисков в столбец C через B, анализ можно выполнить в следующие три шага. * Рассматривайте вышеуказанные n-1 дисков как один диск, поэтому идея анализа согласуется с идеей только о двух дисках, упомянутой выше. * Переместите n-1 дисков выше на B через C * Теперь переместите самый большой диск из-под A в C * Затем переместите n-1 дисков с B на C через A

Кто-то спросил, как переместить n-1 из C в B на первом этапе, повторите описанный выше процесс, просто переместите верхние n-2 пластины в B через A, затем переместите нижнюю пластину A в C и, наконец, переместите пластину. из n - 2 выше перемещается в B через A..., как, вы нашли закономерность, но в процессе поиска проблемыНе расширяйте подзадачи слой за слоем, Когда дело доходит до проблемы Ханойской башни, не анализируйте, как n-3, n-4 двигаются, это вызовет у вас головокружение, пока вы найдете взаимосвязь между слоем проблем и подзадач, вы можете используйте рекурсию, чтобы выразить это.

Из вышеприведенного анализа мы можем получить

move(n from A to C) = move(n-1 from A to B) + move(A to C) + move(n-1 from B to C`)

Обязательно сначала получите рекурсивную формулу, даже если это псевдокод! Таким образом, намного проще написать функцию вывода на третьем шаге. Мы можем легко увидеть условие завершения. Когда диск над A исчезнет, он не будет двигаться.

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

// 将 n 个圆盘从 a 经由 b 移动到 c 上
public void hanoid(int n, char a, char b, char c) {
    if (n <= 0) {
        return;
    }
    // 将上面的  n-1 个圆盘经由 C 移到 B 
    hanoid(n-1, a, c, b);
    // 此时将 A 底下的那块最大的圆盘移到 C
    move(a, c);
    // 再将 B 上的 n-1 个圆盘经由A移到 C上
    hanoid(n-1, b, a, c);
}

public void move(char a, char b) {
    printf("%c->%c\n", a, b);
}

функция от функцииЭто на самом деле легче понять из приведенного выше.Функция всего определения функции состоит в том, чтобы переместить n дисков от A до C через B. Поскольку функция этой функции определена, то переместите n-1 дисков через C. Это очень естественно вызывать эту функцию для B, поэтомуОчень важно четко понимать, что делает функция., объясненный в соответствии с функцией функции, проблему рекурсии на самом деле очень легко проанализировать,Не расширяйте тупиковый слой поверх каждой подзадачи., так что это попадет в ловушку рекурсии, компьютер переполнит стек, не говоря уже о человеческом мозгу

4. Анализ временной сложности Из функции, добавленной на третьем шаге, мы можем сделать вывод, что

f(n) = f(n-1) + 1 + f(n-1) = 2f(n-1) + 1 = 2(2f(n-2) + 1) + 1 = 2 * 2 * f(n-2) + 2 + 1 = 22 * f(n-3) + 2 + 1 = 22 * f(n-3) + 2 + 1 = 22 * (2f(n-4) + 1) = 23 * f(n-4) + 22+ 1 = .... // продолжаем расширяться = 2n-1 + 2n-2 + ....+ 1

Очевидно, временная сложность O(2n), явно экспоненциальная временная сложность неприемлема.Нерекурсивное решение Ханойской башни сложнее.Можно поискать в интернете.

Расширенные вопросы

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

Деление клетки Клетка делится каждый час, по одной дочерней клетке за раз, и умирает через третий час. Итак, сколько клеток имеется в n часов?

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

1. Определить рекурсивную функцию задачи и уточнить функцию функции Определим следующую функцию как количество ячеек через n часов

public int allCells(int n) {
}

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

А на рисунке представляет собой начальное состояние клетки, В представляет собой ювенильное состояние (клетка делится один раз), С представляет собой зрелое состояние (клетка делится дважды), и клетка умирает еще через час С. Пусть f(n) представляет собой количество распадов клеток в n-й час. фa(n) представляет количество клеток в исходном состоянии в n-й час, фb(n) представляет количество клеток в ювенильном состоянии в n-й час фc(n) представляет количество клеток в зрелом состоянии в n-й час тогда, очевидно, f(n) = fa(n) + fb(n) + fc(н) тогда фaЧему равно (n), в качестве примера возьмем n = 4 (т.е. клетка проходит полный жизненный цикл)

Посмотрите внимательно на картинку выше

Как можно видеть фa(n) = fa(n-1) + fb(n-1) + fc(n-1), при n = 1, очевидно, fa(1) = 1

fb(N) сделать, см. Рисунок можно увидеть Fb(n) = fa(N-1). f когда n = 1b(n) = 0

fc(n), посмотрите на рисунок ниже, чтобы увидеть, что fc(n) = fb(n-1). f при n = 1,2c(n) = 0

Подводя итог, мы получаем рекурсивную формулу следующим образом

f(n) = fa(n) + fb(n) + fc(n)

f_a(n)= \begin{cases} f_a(n-1) + f_b(n-1) + f_c(n-1)\\ 1, n = 1 \\ \end{cases}
f_b(n)= \begin{cases} f_a(n-1)\\ 0, n = 1 \\ \end{cases}
f_c(n)= \begin{cases} f_b(n-1)\\ 0, n = 1 \\ 0, n = 2 \\ \end{cases}

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

public int allCells(int n) {
    return aCell(n) + bCell(n) + cCell(n);
}

/**
 * 第 n 小时 a 状态的细胞数 
 */
public int aCell(int n) {
    if(n==1){
        return 1;
    }else{
        return aCell(n-1)+bCell(n-1)+cCell(n-1);
    }
}

/**
 * 第 n 小时 b 状态的细胞数 
 */
public int bCell(int n) {
    if(n==1){
        return 0;
    }else{
        return aCell(n-1);
    }
}

/**
 * 第 n 小时 c 状态的细胞数 
 */
public int cCell(int n) {
    if(n==1 || n==2){
        return 0;
    }else{
        return bCell(n-1);
    }
}

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

4. Найдите временную сложность 由第二步的递推公式我们知道 f(n) = 2aCell(n-1) + 2aCell(n-2) + aCell(n-3)

Временная сложность шагов прыжка лягушки была экспоненциальной, и это уравнение, очевидно, сложнее, чем предыдущая формула рекурсии (f(n) = f(n-1) + f(n-2)), так что это явно экспоненциальный уровень

Суммировать

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

Общественный номер "Код Море", прошу обратить внимание!

Категории