Я сталкивался с рекурсией во время случайных обсуждений, упоминаний в статьях и т. Д. Это было похоже на большую злую волю программирования. Функция, которая вызывает сама себя? Сбивает с толку! Я знал, что рано или поздно пойму это, и на этой неделе наконец настал тот прекрасный день.
В настоящее время я прорабатываю курс Удеми Кольта Стила по структурам данных и алгоритмам (не могу рекомендовать его более строго), и рекурсия - одна из первых тем. Он сломал его таким образом, чтобы убрать паутину путаницы и сделать его чрезвычайно удобным для понимания.
Есть несколько ключевых моментов рекурсии, которые вам нужно усвоить, чтобы концепция имела смысл, и здесь я их рассмотрю.
Общий обзор
Стил рассказывает историю, которую ему рассказали на уроке компьютерной науки много лет назад. Мальчику дается список чисел, и он должен выяснить, есть ли в нем нечетные числа. По какой-то причине единственное существо, которое знает четное и нечетное число, - это скряга-дракон (да, это своего рода странная история, просто продолжайте). Однако, когда мальчик появляется, чтобы попросить дракона оценить его список, дракон отказывается проверять весь список и говорит, что он скажет ему только, четное или нечетное первое число.
Мальчик быстро понимает, что после того, как дракон скажет ему о первом числе, мальчик может убрать это первое число из списка и вернуться к дракону с «новым списком», который на самом деле является просто измененной версией исходного списка. . Он продолжает возвращаться к дракону с этим исправленным списком, пока, наконец, не кончатся числа, и дракон не проверит все числа. Это рекурсия!
Кусочки пазла
Рекурсивная функция состоит из трех основных компонентов.
Первый - это «базовый случай». Это момент, когда функция должна перестать вызывать себя, чтобы не было бесконечного цикла. В приведенном выше примере с драконом базовым случаем будет «когда в списке больше нет номеров» или, в более технических терминах, возможно, что-то вроде list.length === 0 или !list.length.
Второй - это изменяющийся ввод, который передается при вызове рекурсивной функции. Если бы список никогда не менялся, первое число в списке было бы каждый раз одним и тем же, и мальчик никогда не смог бы определить, были ли остальные числа четными или нечетными.
Третье - это собственно действие, которое должно произойти. Дракон проверяет, четное или нечетное число в этом примере.
Поэтому при каждом посещении дракона мальчик удалял первое число из списка, составляя «новый список». Дракон каждый раз делал одно и то же - проверял, было ли первое число четным или нечетным. Но список (ввод) менялся при каждом посещении.
Кажется, это действительно похоже на обычный цикл while, не так ли?
while (some case is true)
do something
change the case (perhaps by incrementing or decrementing)
Собираем все вместе
Давайте сделаем пример с реальным кодом. Учитывая массив чисел, верните сумму всех чисел в массиве. Конечно, мы могли бы сделать это с помощью простого цикла for или .reduce, но цель состоит в том, чтобы использовать рекурсию.
Первое, о чем мы хотим подумать, - это базовый вариант. В какой момент мы хотим, чтобы наш код остановился? В этом примере наша функция должна прекратить выполнение, как только мы дойдем до конца массива и добавим каждый из элементов. Эта часть будет выглядеть так:
Мы хотим иметь оператор return, потому что он завершит выполнение нашей функции и вызовет своего рода каскадный эффект, который мы увидим в действии через мгновение.
Затем мы хотим подумать об изменении ввода и фактическом действии. Действие, которое нам нужно, - это простое добавление. Имея в виду мальчика и дракона, что, если мы просто используем первый элемент массива, а затем отключим этот элемент и добавим первый элемент более нового, меньшего массива, а затем первый элемент еще меньшего массива, и так до конца?
Приведенный ниже GIF выглядит быстро, поэтому вам нужно внимательно смотреть, но давайте разберемся, что происходит. Когда мы впервые вызываем sumOfArray([3,2,1]), мы сначала попадаем в оператор if. Массив не пустой, поэтому мы его обходим и попадаем в строку 3 функции: return array[0] + sumOfArray(array.slice(1)). Slice возвращает копию массива, начиная с указанного индекса. Фактически мы удаляем первый элемент, поскольку мы уже включили его в сумму, и переходим к меньшему массиву.
Теперь наша функция удерживает число 3 и ожидает возвращаемого значения sumOfArray([2,1]) (мы находимся в строке 10 на гифке). Массив не пустой, поэтому мы снова переходим к строке 3 функции. Первый элемент массива теперь равен 2, и нам нужно дождаться возвращаемого значения sumOfArray([1]).
Массив все еще не пустой, поэтому мы переходим к строке 3 функции. Первый элемент массива теперь равен 1, и мы ждем возвращаемого значения sumOfArray([]). Теперь мы наконец достигли «базового случая» пустого массива и вернули 0.
0 теперь передается обратно в предыдущую итерацию функции и добавляется к 1, которая ждала. 1 + 0 равно 1, поэтому 1 возвращается к 2, которая ждала. 2 + 1 равно 3, поэтому 3 передается 3, которая терпеливо ждала с самого начала в строке 10 в гифке. Наконец, 3 + 3 разрешается до 6, что является окончательным возвращаемым значением.
Надеюсь, это немного проясняет рекурсию! По крайней мере, надеюсь, теперь вы сможете получить удовольствие от шуток о рекурсии (они есть повсюду).
Давайте подключимся! Найдите меня в LinkedIn, Twitter и Github.
