🔥Статья «В суть», чтобы полностью понять рекурсию

опрос
🔥Статья «В суть», чтобы полностью понять рекурсию

«Рекурсия» — обычная операция во всех языках, но действительно ли вы хорошо используете рекурсию? У вас нет вопросов о рекурсии? Вы чувствуете, что рекурсия не всегда может найти его и не знаете, как его написать? Эта статья для того

Суть рекурсии — это просто вызовы функций, вы можете легко использовать ее при глубоком понимании принципа, лежащего в ее основе.

Эта статья будет содержать следующее

  • что такое рекурсия
  • Как выбрать условие остановки
  • Природа рекурсии, как работает рекурсия
  • Вопросы для интервью, примеры рекурсивных приложений

Краткое введение

Рекурсия — это общая черта всех языков, а также мощный инструмент для решения многих проблем Итак, что же такое рекурсия?

//最简单的理解，递归就是一个函数调用它自己
function blueFn(){
  blueFn();
}

blueFn();

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

3-报错

Кстати, эта ошибка вызвана "переполнением стека", об этой проблеме мы поговорим подробно позже, продолжим смотреть вниз

конец рекурсии

Никакая операция в программе не может выполняться бесконечно, и рекурсия не является исключением, поэтому рекурсия должна иметь соответствующее «условие завершения» — то есть пока не будет генерироваться новых вызовов. Давайте рассмотрим пример — скажем, мы нужно найти факториал числа n, т.е.5!=5*4*3*2*1Вот что делала начальная школа

function N(num){
  //5! = 5 * 4!
  return num*N(num-1);
}

N(5);

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

4-报错

Почему? Потому что эта функция всегда будет продолжать вызывать вниз, но мы знаем1!На самом деле она "закончена", т.к.1!=1, поэтому мы можем использовать 1 в качестве условия завершения

function N(num){
  if(num<=1)return 1;
  else return num*N(num-1);
}

N(5);

5-正确

Итак, мы видим две наиболее важные особенности рекурсии:

  • Функция вызывает себя (прямо или косвенно)
  • иметь четкие условия завершения

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

Что такое рекурсивное мышление?

Все разделено

первый,Большинство проблем можно разделить на более мелкие проблемы, решая эти небольшие задачи и объединяя результаты вместе, чтобы получить ответ на исходный вопрос, чтобы привести несколько примеров:

  • Подсчет инвентаря: большие склады могут занять месяцы, если подсчитывает один человек.
    • Решение: найдите 20 человек, которые будут отвечать за каждую деталь, а затем сосчитайте их.Сводка результатов
  • Суммирование массива: предположим, что необходимо суммировать 20 ГБ данных, и получение результата занимает много времени.
    • Решение: Найдите 100 машин для совместной работы, каждая из которых отвечает за 200M, а затем поставьте свою собственную.Добавьте результаты
  • Поисковые системы: поисковые системы хранят триллионы страниц, и их поиск на одном сервере занимает много времени, но, по нашему опыту, результаты поиска выдаются за 0,x секунд.
    • Решение: каждый сервер отвечает за часть данных, затемОбъединение частичных результатов поиска в окончательный результат поиска

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

1-问题的分解

Осторожные одноклассники могут сказать: «Эй, учитель, а это не MapReduce от Google?» Да, MapReduce — это приложение по принципу «разделяй и властвуй», но это уже другая тема, поэтому я не буду ее здесь раскрывать.

Пример для понимания рекурсии

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

Давайте посмотрим на вопрос, так легче понять

Примечание. Этот пример упрощает некоторые необходимые операции, чтобы подчеркнуть принцип

Предположим, нам нужна функция, которая поможет нам найтимаксимальное значение

function findMax(arr){
  
}

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

  • Во-первых, мы разделяем массив на левую и правую половины
  • Найдите наибольшее значение слеваmaxL, а затем найти максимальное значение справаmaxR
  • СравниватьmaxLа такжеmaxR, найти окончательный результат max
//注意：严格来说这个函数会有问题，需要判断arr.length才完整——暂略
function findMax(arr){
  //终止条件：数组如果就1个值，它自己就是结果
  if(arr.length==1)return arr[0];
  
  //把数组分成左、右两半
  const center=ceil(arr.length/2);  //取个整，因为下标不能是"2.5"这种
  let arrL=arr.slice(0, center);
  let arrR=arr.slice(center, arr.length);
  
  //找出左侧的最大值`maxL`
  let maxL=findMax(arrL);
  //再找出右侧的最大值`maxR`
  let maxR=findMax(arrR);
  
  //比较`maxL`和`maxR`，找到最终结果max
  if(maxL>maxR)
    return maxL;
  else
    return maxR;
}

В приведенном выше примере мы не решали задачу в лоб, а воспользовались методом «убегания» — рекурсия по сути является разделением задачи и слиянием результатов

  1. Разделите проблему на более мелкие проблемы

    let arrL=arr.slice(0, arr.length/2);
let arrR=arr.slice(arr.length/2, arr.length);

  2. Решить отдельно

    let maxL=findMax(arrL);
let maxR=findMax(arrR);

  3. объединить результаты

    if(maxL>maxR)
  return maxL;
else
  return maxR;

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

Во-первых, предположим, что у нас есть набор данных[12, 8, 96, 27, 3, 9, 81]

2-实例

часть первая, отделение

  • Впервые мы разделим его на две части:[12, 8, 96, 27]а также[3, 9, 81]
  • И приносит два новых вызова функцийfindMax([12, 8, 96, 27])а такжеfindMax([3, 9, 81])
  • Затем каждый массив делится на две части до тех пор, пока дальнейшее разделение становится невозможным.

Вторая часть, слияние

  • каждый раз,findMaxРезультат будет с обеих сторон (например:12а также8) сравниваются, и в качестве результата используется большее из них
  • Повторяйте этот процесс, пока все функции не вернутся, вы можете получить окончательный результат

Природа рекурсии, условие остановки

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

  • Почему переполнение стека? Что такое переполнение стека? Почему он переполнился
  • Как мы должны выбрать условия завершения?

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

Рекурсия на самом деле не является чем-то особенным, это все еще вызов функции, он просто вызывает сам себя (более профессионально, функции «реентерабельны»), поэтому лучший способ понять рекурсию — это сначала понятькак работают функции

стек вызовов функций

js, как и все языки, имеет пространство, предназначенное для хранения вызовов функций в памяти, называемое «стеком вызовов функций».Когда мы вызываем функцию или объявляем локальную переменную, мы манипулируем ею.

Просто посмотрите на программу, давайте посмотрим, как она выполняется

function blueFn(num){
  return sum(12, 5)+num;
}

function sum(a, b){
  return a+b;
}

let res=blueFn(99);
console.log(res+8);

Первый шаг, он будет выполняться со строки 9, когда стек пуст.

7

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

8

Третий шаг, столкнулся с новым вызовом функцииsum(12, 5), перейти на другой уровень

9

Третий шаг, завершениеa+bоперация, и возврат в соответствии с требованиями стека, а затем очистка информации стека

10

Шаг 4, завершение17+numОперация и возврат, конечно же, также очистят информацию о стеке.

11

Наконец, завершитеconsole.log(116+8), вся программа заканчивается

12

В этом процессе мы видим 3 момента:

  • Вызовы функций выполняются через стек
  • Через стек передаются параметры функций, локальные переменные, указатели pc и т. д.
  • Чем глубже уровень вызова функции, тем больше вещей хранится в стеке.

верхний предел стека

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

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

вопросы интервью, примеры

Задача 1. Инверсия массива

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

let arr=[1,2,3];

function reverse(a){
  //在这里具体写东西
}

reverse(arr);  //希望得到反转后的[3,2,1]

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

[1,2,3] -> [3,2,1]

//我们可以看做
1 和 [2,3] -> [3,2] 和 1

//也就是说
arr[0] + arr[1...n] -> reverse(arr[1...n]) + arr[0]

С этой идеей на самом деле очень легко завершить

let arr=[1,2,3];

function reverse(a){
  if(a.length<=1)return a;
  
  const [first, ...rest]=a;
  return [...reverse(rest), first];
}

reverse(arr);

13

Тема 2 - без перебора массива

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

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

function iterate(arr, callback){
  //结束条件
  if(arr.length==0)return;
  
  //把数组分成第一个和其他
  const [first, ...others]=arr;
  
  //自己处理第一个
  callback(first);
  //剩下的递归
  iterate(others);
}

Суммировать

Пришло время разобраться в том, что сказала Блю, так что сначала

15-三连

  • В узком смысле рекурсия — это когда функция вызывает сама себя (прямо или косвенно)
  • В широком смысле рекурсия — это идея, мы можем разбить задачу на маленькие кусочки, решить их по отдельности и, наконец, подвести итог решения всей задачи.
  • Рекурсия и вызовы функций, по сути, предназначены для сохранения информации о вызовах и параметров в стеке вызовов функций (стеке вызовов), а стек вызовов имеет ограничение по размеру, и при превышении стека вызовов будет сообщено об ошибке.
  • Основная проблема рекурсии
    • Как разделить проблему, решить ее по отдельности и объединить результаты
    • Как выбрать подходящие условия завершения (акцент)

Есть ошибка? Хотите добавить?

Спасибо за просмотр этого урока. Если у вас есть какие-либо вопросы или вы хотите связаться с Blue, пожалуйста, оставьте сообщение напрямую. Если вы обнаружите какую-либо неуместность в статье, пожалуйста, укажите на нее, заранее спасибо

Категории