предисловие
Рекурсия — очень важная идея алгоритма, независимо от того, занимаетесь ли вы фронтенд-разработкой или бэкенд-разработкой, вам необходимо освоить ее. В повседневной работе необходимы рекурсивные алгоритмы для подсчета размера папок, парсинга xml файлов и т.д. Это слишком просто и важно, поэтому во время собеседований интервьюеры часто просят нас написать рекурсивные алгоритмы вручную. В этой статье я изучу с вами рекурсивные алгоритмы~
- Что такое рекурсия?
- Особенности рекурсии
- Связь между рекурсией и стеком
- Сценарии рекурсивного приложения
- идеи рекурсивного решения проблем
- пример использования литкода
- Возможные проблемы с рекурсией и решения
адрес github, спасибо за каждую звезду
Общественный номер: маленький мальчик собирает улиток
Что такое рекурсия?
Рекурсия в информатике относится к методу решения проблемы путем многократного разбиения ее на подзадачи одного и того же типа. Проще говоря, рекурсия ведет себя как функция, вызывающая саму функцию. Я видел пример рекурсии метафоры в Zhihu. Лично мне он кажется очень ярким. Давайте посмотрим:
Лучшая аналогия рекурсии — поиск в словаре. Используемый нами словарь сам по себе является рекурсивным, и для объяснения слова необходимо использовать больше слов. Когда вы ищете слово, вы обнаруживаете, что определенное слово в объяснении слова все еще не понимаете, поэтому вы начинаете искать второе слово, но, к сожалению, во втором слове все еще есть слова, которые вы не понимаете. слово, поэтому вы ищете третье слово. Продолжайте поиск таким образом, пока не найдете объяснение слова, которое вы можете полностью понять, затем рекурсия подходит к концу, и тогда вы начинаете отступать и понимать каждое слово, которое у вас есть. проверял раньше, и, наконец, понимаешь значение слова в начале.
Давайте проверим воду и посмотрим пример рекурсивного кода, как показано ниже:
public int sum(int n) {
if (n <= 1) {
return 1;
}
return sum(n - 1) + n;
}
Особенности рекурсии
На самом деле у рекурсии есть две отличительные черты: условие завершения и вызов самого себя:
- Самовызов: Исходная проблема может быть разложена на подзадачи.Подзадача и исходная проблема решаются одинаково, то есть они обе вызывают одну и ту же функцию самих себя.
- Условие завершения: рекурсия должна иметь условие завершения, то есть она не может вызывать себя в бесконечном цикле.
В сочетании с приведенным выше примером демонстрационного кода посмотрите на характеристики рекурсии:
Связь между рекурсией и стеком
На самом деле процесс рекурсии можно понимать как процесс входа и выхода из стека.Эта аналогия приведена только для удобства читателей и друзей, чтобы лучше понять рекурсию. Приведенный выше пример кода вычисляет граф стека суммы (n = 3) следующим образом:
Чтобы было легче понять, давайте посмотрим на рекурсивное выполнение функции sum(n=5) следующим образом:
- При вычислении суммы (5) первая сумма (5) помещается в стек, затем исходная сумма задач (5) разбивается на сумму подзадач (4), а затем помещается в стек до тех пор, пока не будет выполнено условие завершения sum(n). =1)=1. вытолкнуть стек.
- После извлечения суммы (1) начинает появляться сумма (2), а затем сумма (3).
- Наконец, sum(1) входит последним, выходит первым, а sum(5) входит первым, выходит последним, поэтому рекурсивный процесс можно понимать как процесс входа и выхода из стека~
Классический сценарий применения рекурсии
Какие проблемы мы можем рассмотреть, используя рекурсию для решения? То есть каковы общие сценарии применения рекурсии?
- факториальная проблема
- Глубина бинарного дерева
- Проблема с Ханойской башней
- Последовательность Фибоначчи
- Быстрая сортировка, сортировка слиянием (алгоритм «разделяй и властвуй» также реализован рекурсивно)
- Пройдите по файлу и проанализируйте файл xml
идеи рекурсивного решения проблем
Решение рекурсивных задач обычно состоит из трех шагов, а именно:
- Первым шагом является определение функции функции
- Второй шаг — найти условие рекурсивного завершения.
- Второй шаг, отношение эквивалентности рекурсивной функции
Это рекурсивное решение трех осей немного абстрактно для понимания.Давайте возьмем пример факториальной рекурсии, чтобы мяу~
1. Определите функцию функции
Определение функции функции означает, что делает ваша функция, что она делает, другими словами, вам нужно знать, в чем заключается исходная проблема рекурсии? Например, если вам нужно решить проблему факториала, определяемая функция function является факториалом n, как показано ниже:
//n的阶乘（n为大于0的自然数）
int factorial (int n){
}
2. Найдите условие рекурсивного завершения
Типичной особенностью рекурсии является то, что должно быть условие завершения, то есть сам вызов не может быть вызван в бесконечном цикле. Следовательно, при использовании рекурсивного мышления для решения задач необходимо найти условие рекурсивного завершения. Например, в факториальной задаче, когда n=1, нет необходимости рекурсивно дальше, можно выйти из цикла, а n=1 можно использовать как условие завершения рекурсии следующим образом:
//n的阶乘（n为大于0的自然数）
int factorial (int n){
if(n==1){
return 1;
}
}
3. Отношение эквивалентности рекурсивной функции
рекурсивныйпервоначальное значение, то есть исходную задачу можно разбить на аналогичные и более простые для решения подзадачи, а именноИ исходная задача, и подзадача могут быть представлены одним и тем же функциональным отношением. Отношение эквивалентности рекурсивной функции, этот шаг эквивалентен нахождению связи между исходной проблемой и подзадачей, как использовать формулу, чтобы четко выразить эту функцию. Формула для факториала может быть выражена как f(n) = n * f(n-1), поэтому код рекурсивной программы для факториала можно записать следующим образом:
int factorial (int n){
if(n==1){
return 1;
}
return n * factorial(n-1);
}
Внимание, не все отношения эквивалентности рекурсивных функций столь же просты, как факториальные, и могут быть получены сразу. Нам нужно больше контактировать, больше накапливать, больше думать и больше практиковать рекурсивные вопросы~
пример использования литкода
Давайте проанализируем классическую тему рекурсии leetcode~
Оригинальная ссылка здесь:Ли TCO - Talent.com/problems/in…
тема:Перевернуть бинарное дерево.
входить:
4
/ \
2 7
/ \ / \
1 3 6 9
вывод:
4
/ \
7 2
/ \ / \
9 6 3 1
Мы следуем указанным выше трем осям рекурсивного решения проблем:
1. Определите функцию
Функция function (то есть эта рекурсивная исходная задача) задана деревом, а затем переворачивает его, поэтому функцию можно определить как:
//翻转一颗二叉树
public TreeNode invertTree(TreeNode root) {
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
2. Найдите условие рекурсивного завершения
Когда это дерево не будет перевернуто? Конечно, когда текущий узел имеет значение null или текущий узел является конечным узлом. Следовательно, добавление условия завершения:
//翻转一颗二叉树
public TreeNode invertTree(TreeNode root) {
if(root==null || (root.left ==null && root.right ==null)){
return root;
}
}
3. Отношение эквивалентности рекурсивной функции
Для исходной задачи, если вы хотите перевернуть дерево, можете ли вы разбить его на подзадачи и перевернуть его левое и правое поддеревья соответственно? Подзадача переворачивания его левого поддерева может быть разделена на переворачивание левого поддерева его левого поддерева и правого поддерева его левого поддерева? Затем переверните полностью к листовому узлу. Ну, посмотрите на картинку, чтобы понять это~
Во-первых, вы хотите перевернуть дерево с корневым узлом 4, вам нужноПереверните его левое поддерево (корневой узел равен 2) и правое поддерево (корневой узел равен 7).. Это рекурсивносдаватьпроцесс
Тогда дерево, корневой узел которого равен 2, не является конечным узлом, вам нужно продолжитьПереверните его левое поддерево (корневой узел равен 1) и правое поддерево (корневой узел равен 3).. Поскольку узлы 1 и 3 обалистовой узел, так что возвращайся. Это тоже рекурсиясдаватьпроцесс~
Точно так же дерево, корневой узел которого равен 7, не является конечным узлом, вам нужно перевернуть егоего левое поддерево (корневой узел равен 6) и правое поддерево (корневой узел равен 9). Поскольку узлы 6 и 9 являются листовыми узлами, они также возвращаются.
После того, как левое поддерево (корневой узел равен 2) и правое поддерево (корневой узел равен 7) перевернуты, эти шагивозвращение, то есть процесс рекурсивного возврата, задача переворачивания дерева выполнена~
Очевидно,рекуррентное соотношениеэто:
invertTree（root）= invertTree（root.left） + invertTree（root.right）;
Таким образом, легко получить следующий код:
//翻转一颗二叉树
public TreeNode invertTree(TreeNode root) {
if(root==null || (root.left ==null && root.right ==null){
return root;
}
//翻转左子树
TreeNode left = invertTree(root.left);
//翻转右子树
TreeNode right= invertTree(root.right);
}
В этом коде следует обратить внимание на одну вещь: после переворачивания левого и правого поддеревьев дерева также меняются референсные позиции его левого и правого поддеревьев.
root.left = right;
root.right = left;
Таким образом, рекурсивная классическая проблема leetcodeокончательный код решенияследующее:
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null || (root.left ==null && root.right ==null)){
return root;
}
//翻转左子树
TreeNode left = invertTree(root.left);
//翻转右子树
TreeNode right= invertTree(root.right);
//左右子树交换位置~
root.left = right;
root.right = left;
return root;
}
}
Возьмите окончательный код решения в leetcode и отправьте его, передайте его~
проблема рекурсии
- Слишком много уровней рекурсивного вызова, что приводит к проблемам с переполнением стека.
- Рекурсивно повторяющиеся вычисления, приводящие к неэффективности
проблема с переполнением стека
- Каждый вызов функции выделяет место в стеке памяти, а емкость стека каждого процесса ограничена.
- Когда существует слишком много уровней рекурсивных вызовов, емкость стека будет превышена, что приведет к переполнению стека вызовов.
- На самом деле, как мы обсуждали в предыдущем разделе, процесс рекурсии подобен извлечению стека из стека. достаточно.
Пример кода выглядит следующим образом:
/**
* 递归栈溢出测试
*/
public class RecursionTest {
public static void main(String[] args) {
sum(50000);
}
private static int sum(int n) {
if (n <= 1) {
return 1;
}
return sum(n - 1) + n;
}
}
результат операции:
Exception in thread "main" java.lang.StackOverflowError
at recursion.RecursionTest.sum(RecursionTest.java:13)
Как решить эту проблему переполнения стека? Первая потребностьОптимизируйте свою рекурсию, вам действительно нужно так много раз рекурсивно вызывать? Если вам действительно нужно, сначалаУвеличьте объем памяти стека JVM, если это все еще не работает, вам нужно отказаться от рекурсии,Оптимизирован для других решенийВздох~
Повторные вычисления, приводящие к неэффективности программы
Давайте еще раз посмотрим на классическую задачу о прыжках лягушки: лягушка может подпрыгнуть на 1 ступеньку за раз, а может и на 2 ступеньки. Найдите, сколькими способами лягушка может подпрыгнуть на n ступенек.
Подавляющему большинству читателей легко представить себе следующий рекурсивный код:
class Solution {
public int numWays(int n) {
if (n == 0){
return 1;
}
if(n <= 2){
return n;
}
return numWays(n-1) + numWays(n-2);
}
}
Но перейдите в leetcode, чтобы отправить его, есть проблема, он превышает лимит времени
Почему время истекло? Где рекурсия занимает много времени? нарисуй первымдерево рекурсииВзгляни:
- Для вычисления исходной задачи f(10) необходимо сначала вычислить подзадачи f(9) и f(8)
- Затем вычисляется f(9), сначала вычисляются подзадачи f(8) и f(7) и так далее.
- Дерево рекурсии не заканчивается до f(2) и f(1).
Давайте сначала посмотрим на временную сложность этой рекурсии.Сложность времени рекурсии = время решения подзадачи * количество подзадач
- Время подзадачи = f(n-1) + f(n-2), что является операцией сложения, поэтому сложностьO(1);
- Количество проблем = общее количество узлов рекурсивного дерева, итоговая точка рекурсивного дерева = 2 ^ n-1, поэтому сложностьO(2^n).
Следовательно, когда лягушка прыгает, временная сложность рекурсивного решения = O(1) * O(2^n) = O(2^n), что является экспоненциальным и взрывным ростом,Если n относительно велико, тайм-аут нормальный..
Оглядываясь назад, внимательно наблюдая за этим деревом рекурсии, вы обнаружите, чтоМного двойного счета, например, f(8) вычисляется дважды, f(7) повторяется трижды... Таким образом, причина неэффективности этого рекурсивного алгоритма заключается в том, что существует множество повторяющихся вычислений!
Итак, как решить эту проблему?
Так как много повторных вычислений, мы можем сначала сохранить рассчитанные ответы, то есть сделать памятку, и перейти к следующему разу, если он нам понадобится.меморандумПроверьте это, если есть, просто возьмите его напрямую и пересчитайте, если нет памятки, тогда вы можете сэкономить время на пересчет! Эторешение с памяткой
Давайте взглянемрекурсивное решение с памяткойбар~
Обычно в качестве этого используется массив или хеш-карта.меморандум.
Предположим, что f(10) решена плюсмеморандум, снова нарисуем дерево рекурсии:
первый шаг, f(10) = f(9) + f(8), обе f(9) и f(8) необходимо рассчитать и добавить в памятку следующим образом:
Второй шаг,f(9) = f(8) + f(7), f(8) = f(7) + f(6), так как f(8) уже есть в служебной записке, ее можно опустить, f(7) ,f(6) необходимо рассчитать и добавить в памятку~
третий шаг,f(8) = f(7) + f(6), обнаружил, что f(8), f(7), f(6) все есть в памятке, поэтому их можно отрезать.
Итак, используя алгоритм рекурсии мемо, рекурсивное дерево становится голым стволом, как показано ниже:
Рекурсивный алгоритм с «меморандумом», количество подзадач = количеству узлов дерева = n, решение подзадачи по-прежнему составляет O (1), поэтомуВременная сложность рекурсивного алгоритма с «памяткой» составляет O (n).. Затем мы используем рекурсивный алгоритм с «меморандумом» для написания кода для решения проблемы тайм-аута проблемы прыжка лягушки ~, код выглядит следующим образом:
public class Solution {
//使用哈希map，充当备忘录的作用
Map<Integer, Integer> tempMap = new HashMap();
public int numWays(int n) {
// n = 0 也算1种
if (n == 0) {
return 1;
}
if (n <= 2) {
return n;
}
//先判断有没计算过，即看看备忘录有没有
if (tempMap.containsKey(n)) {
//备忘录有，即计算过，直接返回
return tempMap.get(n);
} else {
// 备忘录没有，即没有计算过，执行递归计算,并且把结果保存到备忘录map中，对1000000007取余（这个是leetcode题目规定的）
tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
return tempMap.get(n);
}
}
}
Перейдите в leetcode и отправьте его, как показано на рисунке, он стабилен:
Есть ли другое решение этой проблемы? Толькорекурсивное решение с памяткой? На самом деле, вы также можете использоватьдинамическое программированиерешать
Как решить задачу алгоритма динамического программирования? Мы продолжим в следующем выпуске~ Спасибо за внимание~
Ссылка и спасибо
- [Йивэнь будет решать проблемы рекурсивно] (Tickets.WeChat.QQ.com/is/hew44D8 человек…)
- [Подробное объяснение динамического программирования] (Tickets.WeChat.QQ.com/Yes/1V3ahVOYouW…)
Больше галантереи
Общественный номер: маленький мальчик собирает улиток
- Чтобы узнать больше о галантерее, обратите внимание на публичный аккаунт.
- Ответить в формате pdf, получить обучающую электронную книгу