«Front-end advanced», вы действительно понимаете рекурсию?

алгоритм опрос
«Front-end advanced», вы действительно понимаете рекурсию?

"Видимость: 🌟🌟🌟🌟🌟"

"Вкус: Маосюван"

"Время приготовления: 10 мин."

Эта статья была включена вGithub github.com/Geekhyt, спасибо Стар.

Скоро выйдет третья статья из серии «Структура данных и алгоритмы».Если вы не читали первые две статьи, перейдите по ссылке ниже.

В этой статье мы общаемся рекурсию, рекурсия - это то, почему третья бомба?

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

Природа рекурсии

"Беспомощно упали цветы, и казалось, что Ян вернулся."

Рекурсия, процесс перехода называется «доставкой», а процесс возврата — «возвратом».

Изучение природы рекурсии начинается с изучения природы компьютерных языков.

Суть компьютерного языка — это язык ассемблера, а характеристика языка ассемблера в том, что в нем нет вложенных циклов. Обычно мы используем язык высокого уровня для написанияif..else..да,for/whileЧто ж, на уровне реальных машинных инструкций это простой переход по адресу, переход к определенному месту инструкции, подобноgotoутверждение.

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

Давайте посмотрим на рекурсию из фрагмента кода.

const factorial = function(n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

factorialфункция, реализующая факториал. Берем факториалf(6)Посмотрите на его рекурсию.

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

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

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

1.问题可以被分解成几个子问题

2.问题和子问题的求解方法完全相同

3.递归终止条件

"Стучите по доске и записывайте!"

LeetCode Реальные вопросы

Давайте потренируемся с реальным вопросом LeetCode.

Решите последовательность Фибоначчи, которая начинается с 0 и 1, а каждое последующее число является суммой двух предыдущих, то есть:

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

Учитывая N, вычислить F(N).

Дерево рекурсии показано на рисунке выше, чтобы вычислитьf(5), мы должны сначала вычислить подзадачиf(4)а такжеf(3), вычислятьf(4), необходимо сначала вычислить подзадачиf(3)а такжеf(2)...И так далее, когда, наконец, вычислилиf(0)илиf(1)Когда результат известен, а затем результат возвращается слой за слоем.

После вышеприведенного анализа видно, что три условия рекурсии выполнены, и код запущен.

рекурсивное решение 

const fib = function(n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

Или можно покрасоваться так:

const fib = n => n <= 0 ? 0 : n == 1 ? 1: fib(n - 2) + fib(n - 1);

Это еще не конец, не забудьте выработать привычку и обязательно анализировать сложность алгоритмов, которые вы пишете. Эта часть находится в столбцеАнализ временной и пространственной сложности алгоритма JavaScriptБыло объяснено, студенты, которые не видели его, пожалуйста, нажмите на ссылку, чтобы перейти.

Анализ сложности

  • Сложность пространства O (n)
  • Временная сложность O (2 ^ n)

总时间 = 子问题个数 * 解决一个子问题需要的时间

  • Количество подзадач равно общему количеству узлов в дереве рекурсии 2^n
  • Время, необходимое для решения подзадачи, потому что существует только одна операция сложенияfib(n-1) + fib(n-2), поэтому время решения подзадачи равноO(1)

Умножая два, временная сложность алгоритма равнаO(2^n), Экспоненциальный уровень, треснувший.

Если вы напишете такое решение только во время собеседования, это будет ГГ.

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

(Первоначальная цель выбора этого вопроса — позволить всем понять рекурсию.)

Решение для динамического программирования

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

  • Временная сложность O (n)
  • Пространственная сложность O(1)
const fib = function(n) {
    if (n == 0) {
        return 0;
    }
    let a1 = 0;
    let a2 = 1;
    for (let i = 1; i < n; i++) {
        [a1, a2] = [a2, a1 + a2];
    }
    return a2;
}

Решение формулы общего члена золотого сечения

  • Временная сложность O(logn)
  • Пространственная сложность O(1)
const fib = function(n) {
    return (Math.pow((1 + Math.sqrt(5))/2, n) - Math.pow((1 - Math.sqrt(5))/2, n)) / Math.sqrt(5);
}

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

回到递归，在学习递归的过程中，最大的陷阱就是人肉递归。人脑是很难把整个“递”“归”过程毫无差错的想清楚的。但是计算机恰好擅长做重复的事情，那我们便无须跳入细节，利用数学归纳法的思想，将其抽象成一个递推公式。相信它可以完成这个任务，其他的交给计算机就好了。

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

Когда ты смотришь в бездну, бездна смотрит в тебя.

Прошлые популярные колонки

❤️Любовное тройное комбо

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

2. Обратите внимание на фронтальную столовую официального аккаунта,"Ваша передняя столовая, не забывайте есть вовремя"!

3. Эта статья была добавлена ​​в интерфейсную столовую.Github github.com/Geekhyt, попросите звездочку, поблагодарите звезду.

Категории