Заметки из этого туториала
Этот пост содержит заметки, которые я сделал из это видео freeCodeCamp на YouTube. Я включил все определения (теоретическая часть) и проблемы, решаемые в JavasScript.
Рекурсия: процесс, в котором большая/сложная проблема разбивается на более мелкие подзадачи, и мы решаем эти подзадачи, чтобы решить большую проблему.
Плюсы:
- Преодолевает разрыв между элегантностью и сложностью.
- Снижает потребность в сложных циклах и вспомогательных структурах данных.
- Это может легко уменьшить временную сложность с помощью запоминания.
- Очень хорошо работает с рекурсивными структурами данных, такими как деревья и графики.
Минусы:
- Медлительность из-за перегрузки процессора.
- Может привести к ошибкам нехватки памяти/исключениям StackOverflow.
- Может быть излишне сложным, если плохо построен.
Стек вызовов — это механизм, с помощью которого интерпретатор (например, интерпретатор JavaScript в веб-браузере) отслеживает свое место в сценарии, вызывающем несколько функций — какая функция выполняется в данный момент и какие функции вызываются из этой функции. и т. д. (подробнее здесь…)
Ошибка в стеке вызовов (StackOverflow): это исключение, которое возникает, когда мы превышаем предварительно выделенный буфер памяти, который есть у нашей программы.
Проблемы:
- Перевернуть строку:
- Базовый вариант: если строка пуста, возврат.
- Рекурсивная функция. В противном случае вызовите функцию еще раз для подстроки, начинающейся с индекса 1, и добавьте в конец символ с индексом 0.
2. Палиндром:
- Базовый случай: если длина входной строки равна 0 или 1, возвращается значение true.
- Рекурсивная функция:проверить, равны ли символы в 0-м индексе и последнем индексе (str.length - 1). Снова верните функцию для подстроки от 1-го индекса до предпоследнего индекса строки.
- Вернуть false (еще один базовый случай)
3. Десятичное в двоичное:
- Создайте переменную (результат) для хранения двоичного числа.
- Базовый случай: если десятичное число равно 0, то возвращается результат.
- Операция: добавить (десятичный % 2) к предыдущему значению результата. (результат += десятичный % 2)
- Рекурсивный вызов. Повторно вызовите функцию с частным значением, т. е. decimal/2.
Примечание. Еще один способ рекурсивного преобразования десятичного числа в двоичное.
4. Сумма натуральных чисел:
- Базовый случай: если число равно нулю, вернуть результат.
- Операция и рекурсивный вызов: добавьте текущий номер к рекурсивному вызову функции с помощью num – 1.
5. Двоичный поиск:
- Базовый случай: если левый индекс (меньший) больше правого индекса (больше), возвращается -1.
- Операция: найдите средний индекс и проверьте, равен ли элемент в среднем индексе целевому, затем верните true.
- Рекурсивный вызов:
- Если элемент больше среднего элемента, вызовите функцию с правым индексом, равным середине-1.
- В противном случае вызовите функцию с левым индексом mid+1.
6. Ряд Фибоначчи:
- Базовый случай: если число равно 0 или 1, вернуть число.
- Операция + рекурсивный вызов: вернуть сумму вызова функции с (число-1) и (число-2)
Примечание. Это не оптимизированный способ вычисления n-го числа Фибоначчи.
7. Сортировка слиянием:
- Базовый вариант: вернуть массив, если length(array) ≤ 1.
- Операция: вычислить индекс среднего элемента, т. е. length(array)/2.
- Рекурсивный вызов.Повторный вызов функции от 0-го до середины индекса(левая часть) и от середины индекса до индекса последнего элемента(правая часть).
- Возвратите вспомогательнуюфункцию, которая объединит левую и правую части.
8. Разворот связанного списка:
- Базовый вариант: если head и head.next равны нулю, вернуть head.
- Рекурсивный вызов. Рекурсивно вызовите функцию head.next и сохраните ее в переменной (p).
- Операция:
- Задайте для head.next.next значение head.
- Задайте для head.next значение null.
- Вернуть переменную (p)
9. Объединить два отсортированных связанных списка:даны две головы h1 и h2 в аргументах
- Базовый случай: если h1 и h2 равны нулю, вернуть undefined или, если один из них равен нулю, вернуть другой.
- Рекурсивный вызов + операция:
- Если (h1.value ‹ h2.value) рекурсивно вызвать функцию и установить h1.next как function(h1.next, h2) и вернуть h1.
- В противном случае рекурсивно вызовите функцию и установите h2.next как function(h1, h2.next) и верните h2.
10. Вставьте значение в двоичное дерево поиска:
- Базовый случай: если корень bst равен нулю, установите корень в качестве нового значения.
- Рекурсивный вызов + операция:
- Если (value › root.value), то рекурсивно вызовите функцию на root.right
- В противном случае вызовите функцию на root.left.
11. Распечатайте все конечные узлы:
- Базовый случай: если левый и правый дочерние элементы корня равны нулю, то это конечный узел.
- Рекурсивный вызов:
- Если root.left не равно нулю, вызовите function(root.left)
- Если root.right не равно нулю, вызовите function(root.right)
Запоминание: помогает повысить производительность функций за счет сохранения выходных данных выполнения дорогостоящих в вычислительном отношении функций и возврата кэшированного результата при повторном вызове функции с теми же входными данными.
Рекурсия хвостового вызова: рекурсивная функция является хвостовой рекурсией, когда рекурсивный вызов является последним, что выполняется функцией.
Все исходники:
